regex 检查字符串是否包含指定的模式?[副本]

xtfmy6hx  于 2023-06-25  发布在  其他
关注(0)|答案(1)|浏览(88)

此问题已在此处有答案

Java balanced expressions check {[()]}(37答案)
Can regular expressions be used to match nested patterns? [duplicate](11个答案)
两年前关闭。
这篇文章被编辑并提交审查1年前,未能重新打开帖子:

重复此问题已回答,不唯一,与其他问题没有区别。

我在一次java开发人员的面试中被问到这个问题。
给定一个完全由方括号[]组成的字符串,查找它是否包含模式[*][*][*]。(这里的*表示0或更多的平衡括号字符串)。这意味着,检查它是否有3个或更多的[]内至少任何一个[]
示例:
对于[[][[][][]]],预期答案为true,因为它内部有[][][]
对于[[]][[][]],预期答案为假,因为在[]中的任何一个中,连续[]少于3个
对于[[[]][][[]]],预期答案为真,因为它内部有[..][][..][]中是否有0个或多个[]并不重要。

注意事项:输入字符串已平衡。它不需要检查平衡。

问题是在一个已经平衡的字符串中找到一个特定的嵌套模式。这个问题的输入是一个“balanced”表达式。输出是一个布尔答案,指定它是否包含指定的方括号模式yesno

zujrkrfu

zujrkrfu1#

正则表达式不是解决这类问题的方法。由于递归的原因,它们不能很好地处理嵌套结构。
这是一个完美的问题,例如使用堆栈(FILO)。我建议你看看那些。

class Node
{
    private final Node parent;
    private final List<Node> subNodes = new LinkedList<>();

    Node(Node parent)
    {
        this.parent = parent;
    }

    static Node buildFrom(String str)
    {
        Node start = new Node(null);
        Node current = start;

        for (char ch : str.toCharArray())
        {
            if (ch == '[') //Create new subnode
            {
                Node newNode = new Node(current);
                current.subNodes.add(newNode);
                current = newNode;
            }
            else //Step back
            {
                current = current.parent;
            }
        }
        return start;
    }

    boolean hasTripleNodes()
    {
        if (this.subNodes.size() >= 3) //Found triple+ nodes
        {
            return true;
        }
        else //Continue recursion
        {
            for (Node subNode: this.subNodes)
            {
                if (subNode.hasTripleNodes())
                {
                    return true;
                }
            }
            return false;
        }
    }

    //DEMO
    public static void main(String[] args) throws Exception {
        Node nodes = Node.buildFrom("[[][[][][]]]");
        System.out.println(nodes.hasTripleNodes()); //writes true

        nodes = Node.buildFrom("[[]][[][]]");
        System.out.println(nodes.hasTripleNodes()); //writes false

        nodes = Node.buildFrom("[[[]][][[]]]");
        System.out.println(nodes.hasTripleNodes()); //writes true
    }
}

相关问题