D
DevExCode

LeetCode 3023: Find Pattern in Infinite Stream I Solution

Master LeetCode problem 3023 (Find Pattern in Infinite Stream I), a medium 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.

3023. Find Pattern in Infinite Stream I

Medium
ArraySliding WindowRolling HashString MatchingHash Function

Problem Explanation

Explanation

To solve this problem, we can use the KMP (Knuth-Morris-Pratt) algorithm. We will preprocess the pattern string to generate an array that will help us efficiently find the pattern in the infinite stream of characters. The idea is to match the characters of the pattern against the stream of characters and update the prefix array accordingly to avoid redundant comparisons.

Algorithmic Steps:

  1. Preprocess the pattern string to generate the prefix array using the KMP algorithm.
  2. Initialize a pointer j to keep track of the current character in the pattern.
  3. Iterate over the stream of characters:
    • If the current character matches the pattern character at index j, increment j.
    • If j reaches the end of the pattern, we have found the pattern in the stream.
    • If the current character does not match, update j using the prefix array.
    • Continue this process until we find the pattern or reach the end of the stream.

Time Complexity:

  • Preprocessing the pattern string takes O(m) time, where m is the length of the pattern.
  • Matching the pattern against the stream takes O(n) time, where n is the length of the stream.
  • Thus, the overall time complexity is O(m + n).

Space Complexity:

  • We use O(m) space to store the prefix array.

Solution Code

class FindPatternInInfiniteStreamI {
    public boolean findPattern(String pattern, Stream<Character> stream) {
        int[] prefix = new int[pattern.length()];
        int j = 0;
        
        // Preprocess the pattern string
        for (int i = 1; i < pattern.length(); i++) {
            while (j > 0 && pattern.charAt(i) != pattern.charAt(j)) {
                j = prefix[j - 1];
            }
            if (pattern.charAt(i) == pattern.charAt(j)) {
                prefix[i] = ++j;
            }
        }
        
        // Match pattern against stream
        j = 0;
        for (char ch : stream) {
            while (j > 0 && ch != pattern.charAt(j)) {
                j = prefix[j - 1];
            }
            if (ch == pattern.charAt(j)) {
                if (++j == pattern.length()) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

Try It Yourself

Loading code editor...

Related LeetCode Problems

Frequently Asked Questions

How to solve LeetCode 3023 (Find Pattern in Infinite Stream I)?

This page provides optimized solutions for LeetCode problem 3023 (Find Pattern in Infinite Stream I) 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 3023 (Find Pattern in Infinite Stream I)?

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

Can I run code for LeetCode 3023 on DevExCode?

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

Back to LeetCode Solutions