Word Pattern II

class PatternMatcher {
public:
    bool matchPattern(string pattern, string str) {
        vector<string> mapping(26, "");
        unordered_set<string> usedWords;

        return checkMatch(str, 0, pattern, 0, mapping, usedWords);
    }

private:
    bool checkMatch(string& str, int strIndex, string& pattern, int patIndex,
                    vector<string>& mapping, unordered_set<string>& usedWords) {
        if (patIndex == pattern.size()) {
            return strIndex == str.size();
        }

        char currentChar = pattern[patIndex];

        if (!mapping[currentChar - 'a'].empty()) {
            string existingWord = mapping[currentChar - 'a'];
            if (str.compare(strIndex, existingWord.length(), existingWord)) {
                return false;
            }
            return checkMatch(str, strIndex + existingWord.length(), pattern, patIndex + 1, mapping, usedWords);
        }

        int requiredLength = 0;
        for (int i = patIndex + 1; i < pattern.size(); i++) {
            char tempChar = pattern[i];
            requiredLength += mapping[tempChar - 'a'].empty() ? 1 : mapping[tempChar - 'a'].length();
        }

        for (int end = strIndex + 1; end <= str.size() - requiredLength; end++) {
            string newWord = str.substr(strIndex, end - strIndex);
            if (usedWords.find(newWord) != usedWords.end())
                continue;
            mapping[currentChar - 'a'] = newWord;
            usedWords.insert(newWord);
            if (checkMatch(str, end, pattern, patIndex + 1, mapping, usedWords)) {
                return true;
            }
            mapping[currentChar - 'a'] = "";
            usedWords.erase(newWord);
        }
        return false;
    }
};

The "Word Pattern II" problem requires implementing a method to determine if a given string can be segmented to match a pattern where each character in the pattern corresponds to a non-empty substring in the string. The mapping of characters to substrings must be consistent throughout the pattern.

• The provided solution in C++ uses a backtracking approach to solve this problem.

• The main function, matchPattern, initiates the backtracking with auxiliary functions and data structures. It holds a vector mapping that indexes each letter of the alphabet to map to possible corresponding substrings from the input string. An unordered_set named usedWords keeps track of already used mappings to ensure a word is not reused inappropriately.

• The helper function checkMatch is used recursively to explore valid mappings between segments of the input string and the pattern. It checks if the current part of the pattern can match the current segment of the string:

  • If the end of the pattern is reached and the entire string has been used appropriately, it returns true.
  • If there already exists a mapping for the current character, it verifies the existing mapping against the current segment.
  • If no mapping exists, it tries to create a new mapping by exploring all potential substrings of the remaining string that could match the current pattern character, continually making recursive calls to verify if the rest of the string meets the pattern using the current attempted mapping.

• The function uses effective pruning techniques:

  • It ensures each substring associated with a pattern character is unique by checking the usedWords set.
  • Mappings are reverted if they lead to a dead-end, allowing the algorithm to backtrack and explore alternative possibilities.

This solution gracefully handles the recursive depth and backtracking intrinsically needed for this problem, making it both efficient and comprehensive in finding the correct pattern match or determining its impossibility.

class PatternMatcher {
    public boolean matchPattern(String pattern, String str) {
        String[] wordMap = new String[26];
        Arrays.fill(wordMap, "");
        Set<String> mappedWords = new HashSet<>();

        return matches(str, 0, pattern, 0, wordMap, mappedWords);
    }

    private boolean matches(String str, int indexStr, String pattern, int patternIndex,
                            String[] wordMap, Set<String> mappedWords) {
        if (patternIndex == pattern.length()) {
            return indexStr == str.length();
        }

        char pattChar = pattern.charAt(patternIndex);

        if (!wordMap[pattChar - 'a'].isEmpty()) {
            String matchedWord = wordMap[pattChar - 'a'];
            if (!str.startsWith(matchedWord, indexStr)) {
                return false;
            }
            return matches(str, indexStr + matchedWord.length(), pattern, patternIndex + 1, wordMap, mappedWords);
        }

        int remainingLen = 0;
        for (int i = patternIndex + 1; i < pattern.length(); i++) {
            char nextChar = pattern.charAt(i);
            remainingLen += wordMap[nextChar - 'a'].isEmpty() ? 1 : wordMap[nextChar - 'a'].length();
        }

        for (int k = indexStr + 1; k <= str.length() - remainingLen; k++) {
            String newWord = str.substring(indexStr, k);
            if (mappedWords.contains(newWord))
                continue;
            wordMap[pattChar - 'a'] = newWord;
            mappedWords.add(newWord);
            if (matches(str, k, pattern, patternIndex + 1, wordMap, mappedWords)) {
                return true;
            }
            wordMap[pattChar - 'a'] = "";
            mappedWords.remove(newWord);
        }
        return false;
    }
}

The solution provided is for matching a pattern to a string such that each character in the pattern maps uniquely to a non-empty substring in the string. This Java implementation uses recursion and backtracking to solve the problem.

• Start by initializing wordMap, an array of strings representing the mapping for each character from 'a' to 'z'. Use Arrays.fill to initialize all values to an empty string.
• Employ a HashSet called mappedWords to keep track of which words have already been mapped to avoid mapping multiple pattern characters to the same substring.
• Utilize two main functions: matchPattern() which initializes the variables and calls matches(), and matches() which implements the core of the backtracking and recursion:
  • Verify if the end of the pattern matches the end of the string. If yes, return true.
  • Extract the current pattern character. If it has a mapping in wordMap, check if the corresponding segment of the string fits the expected mapping.
  • If there is no existing mapping, iterate over possible substrings in str that can be assigned to this pattern character:
    • Calculate the remaining length of string needed for the unmapped part of the pattern.
    • Try mapping each reasonable substring to the pattern character and recursively call matches() to proceed further.
    • If a valid complete mapping is found, return true.
    • If the mapping for this substring does not work, revert the changes and continue checking with other substrings.
  • If no valid mappings are found during the iteration, return false.
• Throughout the recursion, add and remove mappings dynamically from mappedWords, updating wordMap accordingly.

This method ensures that all patterns and their corresponding mappings are checked thoroughly through recursion and backtracking, reverting to previous steps if a dead-end is reached, thus exploring all possible mappings.

class Solution:
    def patternMatching(self, pat: str, str_val: str) -> bool:
        char_map = [""] * 26
        used_words = set()

        def matches(si: int, pi: int):
            if pi == len(pat):
                return si == len(str_val)

            pat_char = pat[pi]
            if char_map[ord(pat_char) - ord("a")]:
                mapped_word = char_map[ord(pat_char) - ord("a")]
                if str_val[si: si + len(mapped_word)] != mapped_word:
                    return False
                return matches(si + len(mapped_word), pi + 1)

            required_length = 0
            for i in range(pi + 1, len(pat)):
                if char_map[ord(pat[i]) - ord("a")]:
                    required_length += len(char_map[ord(pat[i]) - ord("a")])
                else:
                    required_length += 1

            for end in range(si + 1, len(str_val) - required_length + 1):
                candidate_word = str_val[si:end]
                if candidate_word in used_words:
                    continue
                char_map[ord(pat_char) - ord("a")] = candidate_word
                used_words.add(candidate_word)
                if matches(end, pi + 1):
                    return True
                char_map[ord(pat_char) - ord("a")] = ""
                used_words.remove(candidate_word)
            return False

        return matches(0, 0)

This Python solution addresses the problem of matching a given string pattern with a string str_val using backtracking. It implements a function patternMatching that takes a pattern and a string and determines if the string matches the pattern. Here is a breakdown of how the implemented solution works:

• Initialization: Two structures are initialized: char_map to store character-to-word mappings from the pattern to the string and used_words to keep track of words already mapped to ensure uniqueness.

• Recursive Function matches: This is the core of the solution, executing the backtracking algorithm.

  • Base Case: If the entire pattern has been processed (pi equals the length of the pattern), the function checks if all the string has also been matched (si equals the length of the string) and returns True or False accordingly.
  • Mapped Pattern Character: If the pattern character at index pi has already been mapped, it checks whether the next part of str_val matches the mapped word. If not, it returns False; otherwise, it moves on to check the rest of the pattern and the string.
  • Unmapped Pattern Character: For an unmapped character, the code iterates over possible segments of str_val that could be matched to it, being mindful of the length required for subsequent pattern characters.
    • The function checks new segments against used_words. If a new valid mapping is found, the mapped segment is tested for the rest of the string. If the rest matches, it returns True; if not, it reverts the changes and continues checking other possible segments.

• Return Result: The function returns the result of the initial call to matches which starts the recursive checking process.

This solution effectively uses a combination of a dictionary (char_map) and a set (used_words) to attempt creating a bijective mapping between pattern characters and substring words in str_val. By systematically exploring all possible mappings and backtracking upon failures, the function ensures that the solution space is thoroughly examined.