Wildcard Matching

class Solution {
public:
    bool doesMatch(string str, string pat) {
        int strLen = str.size(), patLen = pat.size();
        int strIndex = 0, patIndex = 0;
        int lastStarIndex = -1, savedStrIndex = -1;
        while (strIndex < strLen) {
            if (patIndex < patLen && (pat[patIndex] == '?' || pat[patIndex] == str[strIndex])) {
                ++strIndex;
                ++patIndex;
            } else if (patIndex < patLen && pat[patIndex] == '*') {
                lastStarIndex = patIndex;
                savedStrIndex = strIndex;
                ++patIndex;
            } else if (lastStarIndex == -1) {
                return false;
            } else {
                patIndex = lastStarIndex + 1;
                strIndex = savedStrIndex + 1;
                savedStrIndex = strIndex;
            }
        }
        for (int i = patIndex; i < patLen; i++) {
            if (pat[i] != '*') return false;
        }
        return true;
    }
};

The given C++ solution involves a method named doesMatch which is designed to determine if a string str matches with a pattern pat containing wildcard characters. It effectively handles '*' which matches any number of any characters, including none, and '?' which matches any single character.

Here's a breakdown of how the function operates:

• It starts by initializing variables for the length of the string and pattern (strLen and patLen), and indices to iterate through both the string and the pattern (strIndex and patIndex). Additionally, lastStarIndex and savedStrIndex help to track positions related to the * character in the pattern.

• Using a while loop, the function iterates through the string, checking characters against the pattern:

  • If the current characters in the string and pattern match (direct match or '?'), both indices are incremented to continue the comparison.

  • When encountering a * in the pattern, the function memorizes this position (lastStarIndex) along with the corresponding string position (savedStrIndex), then advances the pattern index to check for subsequent characters.

  • If a mismatch occurs and no previous * has been encountered (lastStarIndex is -1), the function concludes the string doesn't match the pattern, returning false.

  • If a mismatch occurs but a * was previously encountered, the indices roll back to the positions stored plus one, and the comparison continues. This effectively analyzes the string for different subsequences that might follow after a *.

• Post-loop, the function ensures all remaining characters in the pattern are *. Otherwise, it means there's a mismatch and returns false.

• Finally, if all conditions are satisfied, the function returns true, indicating the string fully matches the pattern including wildcards.

This solution is efficient for cases with multiple continuous wildcard characters and is capable of handling complex pattern matchings with different positions of wildcards effectively.

class Solution {
    public boolean matchPattern(String str, String pattern) {
        int strLength = str.length(), patLength = pattern.length();
        int strIndex = 0, patIndex = 0;
        int lastStarIndex = -1, tempStrIndex = -1;
    
        while (strIndex < strLength) {
            if (
                patIndex < patLength &&
                (pattern.charAt(patIndex) == '?' || pattern.charAt(patIndex) == str.charAt(strIndex))
            ) {
                ++strIndex;
                ++patIndex;
            } else if (patIndex < patLength && pattern.charAt(patIndex) == '*') {
                lastStarIndex = patIndex;
                tempStrIndex = strIndex;
                ++patIndex;
            } else if (lastStarIndex == -1) {
                return false;
            } else {
                patIndex = lastStarIndex + 1;
                strIndex = tempStrIndex + 1;
                tempStrIndex = strIndex;
            }
        }
    
        for (int i = patIndex; i < patLength; i++) {
            if (pattern.charAt(i) != '*') {
                return false;
            }
        }
        return true;
    }
}

The provided Java code implements a solution for the "Wildcard Matching" problem. This function attempts to determine if a given string (str) matches a pattern (pattern) where the pattern may include wildcard characters ? and *. Here's how it works step-by-step:

1. Start by initializing pointers for both the string and the pattern, as well as indices to track the last occurrence of * in the pattern and its corresponding position in the string.
2. Loop through the string with the help of the string index. Compare the current characters of the string and the pattern.
3. If the characters match directly or if the pattern character is a ?, which matches any single character, move both indices forward.
4. If the pattern character is a *, it may match any sequence including an empty sequence:
   • Mark this position for the pattern index.
   • Keep the corresponding string index in memory.
   • Move the pattern index forward to continue checking.
5. If no direct character match or valid wildcard scenario is found and there's no previous * to fallback to, return false since the pattern can't match the string.
6. If you exited the loop because a * was found but some characters remain after all possible matches have been considered, backtrack. Adjust the indices to explore different lengths of sequences that can be matched by *, and continue processing.
7. After exiting the loop, check for any remaining characters in the pattern:
   • If they are all *, they don't affect the match result as they can represent empty sequences.
   • If any other character remains, return false as there can't be a match.
8. Return true if all conditions are satisfied meaning the pattern matches the string fully.

The algorithm effectively handles matches involving wildcards and this approach ensures all possible ways to match sequences represented by * are explored by backtracking. It smartly leverages indicators to remember prior states when a potential match involving a wildcard could fail later, hence gracefully going back and trying different possibilities.

bool patternMatch(char* str, char* pattern) {
    int strLen = strlen(str), patLen = strlen(pattern);
    int strIndex = 0, patIndex = 0;
    int lastStarIndex = -1, tempStrIndex = -1;
    while (strIndex < strLen) {
        if (patIndex < patLen && (pattern[patIndex] == '?' || pattern[patIndex] == str[strIndex])) {
            strIndex++;
            patIndex++;
        }
        else if (patIndex < patLen && pattern[patIndex] == '*') {
            lastStarIndex = patIndex;
            tempStrIndex = strIndex;
            patIndex++;
        }
        else if (lastStarIndex == -1) {
            return false;
        }
        else {
            patIndex = lastStarIndex + 1;
            strIndex = tempStrIndex + 1;
            tempStrIndex = strIndex;
        }
    }
    for (int i = patIndex; i < patLen; i++) {
        if (pattern[i] != '*') {
            return false;
        }
    }
    return true;
}

The provided C program implements a method patternMatch for wildcard matching, where str is the input string and pattern is the wildcard pattern including characters ? and *. Here's a high-level overview of how this function operates:

• Initializes variables for the lengths of the string and the pattern, indices for traversing through both, and helpers to manage positions related to the * wildcard.
• Uses a loop to iterate through the string. Within the loop:
  • Matches characters directly or ? which represents any single character.
  • Handles * by marking its position and the current string index. It allows the pattern to skip over an arbitrary sequence of characters in the string.
  • If a mismatch occurs and no previous * can compensate (handled by backtracking to the last * position), the function returns false.
• Post loop, clears any trailing * in the pattern, as they can match an empty sequence.
• If the end of both the string and the pattern is reached successfully, returns true. If any non-* characters remain in the pattern after processing the entire string, returns false.

This implementation effectively solves the wildcard matching problem by utilizing a combination of direct comparison, character substitution for ?, and sequence matching for *. The use of backtracking enables it to handle cases where multiple * characters appear in the pattern, ensuring all possible matching options are explored.

var stringMatchPattern = function (str, pattern) {
    let strLen = str.length,
        patternLen = pattern.length;
    let strIndex = 0,
        patternIndex = 0;
    let asteriskIndex = -1,
        strTempIndex = -1;
    while (strIndex < strLen) {
        if (patternIndex < patternLen && (pattern[patternIndex] === "?" || pattern[patternIndex] === str[strIndex])) {
            ++strIndex;
            ++patternIndex;
        }
        else if (patternIndex < patternLen && pattern[patternIndex] === "*") {
            asteriskIndex = patternIndex;
            strTempIndex = strIndex;
            ++patternIndex;
        }
        else if (asteriskIndex === -1) {
            return false;
        }
        else {
            patternIndex = asteriskIndex + 1;
            strIndex = strTempIndex + 1;
            strTempIndex = strIndex;
        }
    }
    for (let i = patternIndex; i < patternLen; i++) {
        if (pattern[i] !== "*") {
            return false;
        }
    }
    return true;
};

The JavaScript function stringMatchPattern checks if a given string str matches a pattern pattern that includes wildcards. This pattern may contain characters, ? which matches any single character, and * which matches any sequence of characters (including an empty sequence). The function implements a solution utilizing two-pointers and backtracking to handle the complexity introduced by the * wildcard.

• Initialize variables to handle the length of the string and pattern, indices for both, and keep track of the last positions of * and mismatch in the string.

• Iterate through the string using a while loop:

  • If the current characters match or the pattern has ?, move both indices forward.
  • If the current pattern character is *, record this position and the current string index, then move the pattern index forward.
  • If there is a mismatch, and no previous * is found, return false since the pattern cannot match the string.
  • If a mismatch occurs but there was a prior *, reset to the indices right after the * and the matched part of the string, then continue.

• After the main loop, check the remaining characters in the pattern. If any are not *, return false because these extra characters cannot be matched with the end of the string.

• If all conditions are met, return true as the entire string matches the pattern.

This algorithm efficiently manages pattern matching by allowing backtracking when a wildcard * is present, hence accommodating complex matching scenarios while ensuring all parts of the string are appropriately matched or allowed to be skipped.

class Solution:
    def pattern_match(self, txt: str, pat: str) -> bool:
        txt_len, pat_len = len(txt), len(pat)
        txt_index = pat_index = 0
        last_star = temp_index = -1
    
        while txt_index < txt_len:
            # Match char directly or by '?'
            if pat_index < pat_len and pat[pat_index] in ["?", txt[txt_index]]:
                txt_index += 1
                pat_index += 1
    
            # Handle '*' in pattern
            elif pat_index < pat_len and pat[pat_index] == "*":
                last_star = pat_index
                temp_index = txt_index
                pat_index += 1
    
            elif last_star == -1:
                return False  # No star to fall back to
    
            else:
                pat_index = last_star + 1
                txt_index = temp_index + 1
                temp_index = txt_index
    
        # Verify remaining pattern is all '*'
        return all(pat[i] == "*" for i in range(pat_index, pat_len))

This Python solution tackles the "Wildcard Matching" problem, aiming to determine if a string txt matches the pattern pat, which includes characters like ? and *. The ? character in pat can match any single character in txt, while * can match any sequence of characters, including an empty sequence.

Here's a breakdown of how the solution operates:

1. Initialize indices for the text (txt_index) and pattern (pat_index), and set helper variables last_star and temp_index to handle positions related to the * character.
2. Use a while loop to process characters in txt. Inside the loop:
   • Match characters directly or with ?.
   • If encountering a * in pat, record this position with last_star and set temp_index to the current txt_index.
   • If there is no matching position and no previous * to fall back on, return False.
   • If there is a previously encountered *, adjust pat_index and shift txt_index accordingly to attempt new matches.
3. After exiting the loop, check any remaining characters in pat. If all are *, the function returns True; otherwise, it returns False.

This implementation effectively handles wildcard matching by adapting to both specific character replacements and flexible sub-sequence substitutions using the features of Python.