LeetCode 3037: Find Pattern in Infinite Stream II Solution

Master LeetCode problem 3037 (Find Pattern in Infinite Stream II), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

3037. Find Pattern in Infinite Stream II

Hard

Array Sliding Window Rolling Hash String Matching Hash Function

Problem Explanation

Explanation:

This problem involves finding if a given pattern exists in an infinite stream of characters. The pattern can contain lowercase letters, uppercase letters, and digits. The pattern can also have a wildcard character '*', which can match any sequence of characters.

To solve this problem efficiently, we can use a Trie data structure. Each node in the Trie represents a character in the pattern. We will also maintain a set of pointers that represent the current state of the Trie for each character in the pattern.

Whenever we receive a new character from the stream, we will update each pointer to the next state based on the current character. If a pointer reaches the end state in the Trie, it means that the pattern exists in the stream up to that point.

: :

Solution Code

class TrieNode {
    Map<Character, TrieNode> children;
    boolean isEnd;

    public TrieNode() {
        children = new HashMap<>();
        isEnd = false;
    }
}

class StreamChecker {
    TrieNode root;
    Set<TrieNode> pointers;

    public StreamChecker(String[] words) {
        root = new TrieNode();
        pointers = new HashSet<>();
        
        for (String word : words) {
            TrieNode node = root;
            for (int i = word.length() - 1; i >= 0; i--) {
                char c = word.charAt(i);
                if (!node.children.containsKey(c)) {
                    node.children.put(c, new TrieNode());
                }
                node = node.children.get(c);
            }
            node.isEnd = true;
        }
    }

    public boolean query(char letter) {
        boolean found = false;
        Set<TrieNode> newPointers = new HashSet<>();

        pointers.add(root);
        for (TrieNode node : pointers) {
            if (node.children.containsKey(letter)) {
                TrieNode nextNode = node.children.get(letter);
                newPointers.add(nextNode);
                if (nextNode.isEnd) {
                    found = true;
                }
            }
        }
        
        pointers = newPointers;
        return found;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 3037 (Find Pattern in Infinite Stream II)?

This page provides optimized solutions for LeetCode problem 3037 (Find Pattern in Infinite Stream II) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 3037 (Find Pattern in Infinite Stream II)?

The time complexity for LeetCode 3037 (Find Pattern in Infinite Stream II) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 3037 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 3037 in Java, C++, or Python.

Back to LeetCode Solutions