3407. Substring Matching Pattern

EasyStringString Matching

Problem Description

You are given a string s and a pattern string p, where p contains exactly one '*' character. The '*' in p can be replaced with any sequence of zero or more characters. The task is to determine if p can be transformed into a substring of s by replacing '*' with an appropriate sequence of characters. The function should return true if such a transformation is possible, or false otherwise.

Intuition

The key to solving this problem efficiently is recognizing that the '*' in the pattern p allows us to match with any sequence of characters. Therefore, the problem reduces to checking if the parts of p around the '*' can be found consecutively in s.

Splitting the Pattern: First, split the pattern p into two parts using the '*' as a delimiter. This yields the segments you need to match with the string s.
Sequential Matching: Iterate through each of these segments and check if they can be found in s in the same order. This involves:
- Searching for each segment in s starting from the point where the previous segment ended.
- If a segment cannot be found, it immediately implies that p cannot be formed as a substring of s.
Check Continuity: If all segments are found in their correct order, then p can indeed be transformed into a substring of s. This approach efficiently leverages the built-in string operation find, to check for the presence of segments in s.

By using these steps, the solution efficiently verifies the condition by focusing just on the parts of p that need to be found, rather than attempting to replace and match every possible combination of characters represented by '*'.

Solution Approach

The provided solution utilizes a straightforward approach to determine if the pattern p can be transformed into a substring of s. Here's a step-by-step explanation of the algorithm used in the solution:

Split the Pattern:
- The pattern p is split into two parts using the '*' character as a delimiter. This is achieved with p.split("*"), which results in a list of strings.
Iterate Through the Pattern Parts:
- Initialize an index i to track the position in the string s from where to start searching for each subsequent part of the pattern.
- For each part t in the split list of p:
  - Attempt to find the position of t in s, starting from the index i, using s.find(t, i).
  - If the part t cannot be found (.find returns -1), return False immediately.
Update the Index:
- If the part t is found, update i to the position right after where t ends (j + len(t)). This ensures the subsequent segments start searching after the previous match.
Final Verdict:
- If all parts are found in sequence within s, the function returns True, indicating that p can indeed form a substring of s.

This approach efficiently checks for the possibility by piecing together the non-star sections of p within s step-by-step, leveraging the find function to make targeted checks rather than attempting to simulate the pattern replacement for every possible sequence.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through an example to illustrate the solution approach:

Consider the string s = "helloworld" and the pattern p = "he*world".

Split the Pattern:
Split p using the '*' character as the delimiter. This results in two parts: ["he", "world"].
Iterate Through the Pattern Parts:
- Initialize an index i = 0 to start searching in the string s.
- First Part "he":
  - Search for "he" in s, starting from index 0.
  - "he" is found starting at index 0. Update the index i to 0 + len("he") = 2.
- Second Part "world":
  - Search for "world" in s, starting from index 2.
  - "world" is found starting at index 5. Update the index i to 5 + len("world") = 10.
Final Verdict:
- Both parts "he" and "world" are sequentially found in s. Thus, return True.

In this example, the non-star parts of the pattern "he" and "world" are found in the string s in sequence, confirming that p can indeed be transformed into a substring of s.

Solution Implementation

1class Solution:
2    def hasMatch(self, s: str, p: str) -> bool:
3        # Initialize the starting index for search in string `s`
4        i = 0
5      
6        # Split the pattern `p` by '*' to get the substrings that need to match
7        for t in p.split("*"):
8            # Find occurrence of substring `t` in `s` starting from index `i`
9            j = s.find(t, i)
10            # If `t` is not found in `s`, return False immediately
11            if j == -1:
12                return False
13            # Update `i` to point just after the matched substring `t`
14            i = j + len(t)
15      
16        # If all substrings in pattern `p` are found in sequence, return True
17        return True
18

1class Solution {
2    public boolean hasMatch(String s, String p) {
3        // Initialize the starting index in the string s
4        int currentIndex = 0;
5      
6        // Split the pattern p by '*' and iterate over each substring
7        for (String subPattern : p.split("\\*")) {
8            // Find the index of the current subPattern in s starting from currentIndex
9            int matchIndex = s.indexOf(subPattern, currentIndex);
10          
11            // If subPattern is not found in s, return false
12            if (matchIndex == -1) {
13                return false;
14            }
15          
16            // Update currentIndex to the end of the matched subPattern
17            currentIndex = matchIndex + subPattern.length();
18        }
19      
20        // All subPatterns were found in sequence, hence return true
21        return true;
22    }
23}
24

1class Solution {
2public:
3    bool hasMatch(string s, string p) {
4        int currentIndex = 0; // Current position in the string 's'
5        int position = 0;     // Position of found substring
6        int start = 0, end;   // Variables to track the start and end of each segment in pattern 'p'
7
8        // Loop until a "*" is found in pattern 'p'
9        while ((end = p.find("*", start)) != string::npos) {
10            // Extracting the substring from 'p' between 'start' and 'end'
11            string subPattern = p.substr(start, end - start);
12          
13            // Find this substring in 's', starting search from 'currentIndex'
14            position = s.find(subPattern, currentIndex);
15          
16            // If the substring is not found, return false
17            if (position == string::npos) {
18                return false;
19            }
20          
21            // Move currentIndex to the end of the found substring
22            currentIndex = position + subPattern.length();
23          
24            // Move start past the "*" character in 'p'
25            start = end + 1;
26        }
27      
28        // Handle the remaining part of the pattern 'p' after the last "*"
29        string subPattern = p.substr(start);
30      
31        // Check if the remaining part of 'p' is found in 's'
32        position = s.find(subPattern, currentIndex);
33      
34        // If not found, return false, else return true
35        return position != string::npos;
36    }
37};
38

1// Function to determine if the string `s` matches the pattern `p`
2// where `p` can include '*' as a wildcard character.
3function hasMatch(s: string, p: string): boolean {
4    // Initialize the starting index for searching in `s`.
5    let i = 0;
6
7    // Split the pattern `p` by the wildcard '*' and iterate over each split part.
8    for (const part of p.split('*')) {
9        // Find the index of the current `part` in the string `s`, starting from index `i`.
10        const foundIndex = s.indexOf(part, i);
11
12        // If `part` is not found in `s`, return false as the pattern doesn't match.
13        if (foundIndex === -1) {
14            return false;
15        }
16      
17        // Update the index `i` to be just past the end of the found `part`.
18        i = foundIndex + part.length;
19    }
20  
21    // If all parts of `p` were found in `s` in order, return true.
22    return true;
23}
24

Time and Space Complexity

The given code's time complexity is O(n * m), where n is the length of the string s, and m is the number of segments created after splitting p by "*". This complexity arises because for each segment in p, a search is performed in s using find, which can take up to O(n) time in the worst case.

The space complexity of the code is O(m), where m is the number of parts in p after splitting by "*", due to the storage required for the segmented parts of the pattern p.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

What's the output of running the following function using the following tree as input?

1def serialize(root):
2    res = []
3    def dfs(root):
4        if not root:
5            res.append('x')
6            return
7        res.append(root.val)
8        dfs(root.left)
9        dfs(root.right)
10    dfs(root)
11    return ' '.join(res)
12

1import java.util.StringJoiner;
2
3public static String serialize(Node root) {
4    StringJoiner res = new StringJoiner(" ");
5    serializeDFS(root, res);
6    return res.toString();
7}
8
9private static void serializeDFS(Node root, StringJoiner result) {
10    if (root == null) {
11        result.add("x");
12        return;
13    }
14    result.add(Integer.toString(root.val));
15    serializeDFS(root.left, result);
16    serializeDFS(root.right, result);
17}
18

1function serialize(root) {
2    let res = [];
3    serialize_dfs(root, res);
4    return res.join(" ");
5}
6
7function serialize_dfs(root, res) {
8    if (!root) {
9        res.push("x");
10        return;
11    }
12    res.push(root.val);
13    serialize_dfs(root.left, res);
14    serialize_dfs(root.right, res);
15}
16

1 2 3 6 x x

1 2 3 x x x 6 x x

1 2 6 x x x 3 x x

I don’t know