Check whether a string contains a specified pattern?

Question

I've been asked this question in a java dev interview.

Given a string entirely made of square brackets [ and ], find if it has the pattern [*][*][*] inside. (the * here represents a 0 or more balanced bracket strings). meaning, check if it has 3 or more of[] inside at-least any one of[].

Examples:

for [[][[][][]]] expected answer is true as it has [][][] inside it.

for [[]][[][]] expected answer is false as it has less than 3 consecutive [] inside any one of []

for [[[]][][[]]] expected answer is true as it has [..][][..] inside it. It doesn't matter if there are 0 or more [] inside a [] .

IMPORTANT: The input string is already balanced. It doesn't need to checked for balance.

The question is to find a specific nested pattern inside an already balanced string. The input to this problem is a "balanced" expression. The output is a boolean answer specifying whether it contains the specified pattern of brackets yes or no.

@Pshemo the open and closing brackets may be nested , so simple contains won't work. See example 3 for clarification — NoobScript, May 01 '21 at 13:39
In that case you probably need to explain it farther in problem description. Also `[*][*][*]` isn't clear since `*` has very specific meaning in regex which you probably didn't meant in that example. — Pshemo, May 01 '21 at 13:42
Your first example is not balanced. Should it still return true? — NomadMaker, May 01 '21 at 13:48
@NomadMaker i screwed up, it is balanced, i'll edit the question. The input is always balanced. — NoobScript, May 01 '21 at 13:53
Shouldn't second case match `[*][*][*]`? Notice that `[[]][[][]]` can be split into `[[]]` `[[]` `[]]` (each of those parts can match `[*]` - assuming that `*` represents *any string*). — Pshemo, May 01 '21 at 13:59
@Pshemo the * represents a balanced bracket expression. I'll edit the question to make it clear — NoobScript, May 01 '21 at 14:02

score 1 · Answer 1 · edited May 01 '21 at 14:26

1

Regular expressions are not the way to go for this kind of problem. They don't work particularly well with nested structures because of recursion.

This is a prefect problem for using stacks (FILO) for example. I'd recommend you take a look at those.

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
    }
}

edited May 01 '21 at 14:26

Pshemo

122,468
25
185
269

answered May 01 '21 at 13:45

Richard Nagy

141
9

I know how to use stacks to check if it is balanced, but i can't figure out how to use that in this particular case. Can u guide me to a similar problem or any suggestion on how to get started – NoobScript May 01 '21 at 13:48
On further reading of the question I think you'd be better off using some kind of tree structure. Represent each bracket (pair) as a node and create sub-nodes for each bracket (pair) you find in it. If in the final tree there is any single node with 3 or more subnodes, then it fits your criteria. – Richard Nagy May 01 '21 at 13:53
Can u give me idea on how to construct this tree.I can't comprehend how to have root node of the tree that is concatenated first and last character of a given string. – NoobScript May 01 '21 at 13:59
@NoobScript: When I am checking my code for balanced parentheses, I generally read my code left to right, count up by one for each left parenthesis, and count down for each right parenthesis. If I reach zero by the time I get to the end of my line of code, the parentheses are balanced. Maybe you could do something similar in your code? – Robert Harvey May 01 '21 at 14:12
I added my code. Basically all you do is create a new subnode and step into it on an opening bracket, or step out on a closing bracket – Richard Nagy May 01 '21 at 14:13
@RobertHarvey the input is already balanced. The problem is to find if a node has more than 2 children if the input is represented as a tree – NoobScript May 01 '21 at 14:14
@DavidBose thanks, this looks like it could work. – NoobScript May 01 '21 at 14:16
Cheers! Have fun with it – Richard Nagy May 01 '21 at 14:19
whoever marked this question as a duplicate of balanced expression check, please explain why you though it is. The question makes it very clear that it has nothing to with balancing. – NoobScript Aug 26 '21 at 13:49

Check whether a string contains a specified pattern?

1 Answers1