Question

Formatted question description: https://leetcode.ca/all/291.html

 291	Word Pattern II

 Given a pattern and a string str, find if str follows the same pattern.

 Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty substring in str.

 Examples:

 pattern = "abab", str = "redblueredblue" should return true. (a->red, b->blue)
 pattern = "aaaa", str = "asdasdasdasd" should return true. (a->asd)
 pattern = "aabb", str = "xyzabcxzyabc" should return false.

 Notes:
 You may assume both pattern and str contains only lowercase letters.

Algorithm

To use HashMap to establish the mapping between pattern characters and words, you also need to use variables p and r to record the position of the pattern character and word string currently recursed to.

  • In the recursive function, if p and r are equal to the length of the pattern string and the word string respectively, it means that the matching has ended successfully at this time, and ture is returned.
  • On the contrary, if one is reached and the other is not, it means that the match has failed, and false is returned.
  • If the above conditions are not met, take out the pattern character at the current position, and then traverse backward from position r of the word string, taking out one word each time,
    • If the pattern character already exists in the HashMap, and the corresponding word and the extracted word are also equal, then call the recursive function again in the next position,
      • If it returns true, then return true.
    • On the contrary, if the pattern character is not in the HashMap, it depends on whether other pattern characters have been mapped to the word currently taken out.
      • If not, create a new mapping and call the recursive function
      • Note that if the recursive function returns false, delete this mapping in the HashMap

Pitfall

Don’t forget below part during DFS.

map.remove(patternChar); // @note: need to remove, since this attempt is failed
inverseMap.remove(tentativeMatchString);

Code

Java

  • import java.util.HashMap;
    
    public class Word_Pattern_II {
    
        public static void main(String[] args) {
            Word_Pattern_II out = new Word_Pattern_II();
            Solution s = out.new Solution();
    
            System.out.println(s.wordPattern("abab", "redblueredblue"));
            System.out.println(s.wordPattern("aaaa", "asdasdasdasd"));
            System.out.println(s.wordPattern("aabb", "xyzabcxzyabc"));
            System.out.println(s.wordPattern("aaaa", "asdyyyasdyyy")); // false
        }
    
    
        public class Solution {
    
            public boolean wordPattern(String pattern, String str) {
    
                HashMap<Character, String> map = new HashMap<>();
                HashMap<String, Character> inverseMap = new HashMap<>();
    
                return dfs(pattern, 0, str, 0, map, inverseMap);
            }
    
            // p: pattern length
            // r: word length
            boolean dfs(String pattern, int pattenIndex, String str, int strIndex, HashMap<Character, String> map, HashMap<String, Character> inverseMap) {
    
                if (pattenIndex == pattern.length() && strIndex == str.length()) {
                    return true;
                }
                if (pattenIndex == pattern.length() || strIndex == str.length()) { // didn't hit above if but this one
                    return false;
                }
    
                char patternChar = pattern.charAt(pattenIndex);
    
                for (int i = strIndex; i < str.length(); ++i) {
                    String tentativeMatchString = str.substring(strIndex, i + 1);
    
                    if (map.containsKey(patternChar) && map.get(patternChar).equals(tentativeMatchString) && inverseMap.containsKey(tentativeMatchString) && inverseMap.get(tentativeMatchString).equals(patternChar)) {
                        if (dfs(pattern, pattenIndex + 1, str, i + 1, map, inverseMap)) {
                            return true;
                        }
    
                    } else if (!map.containsKey(patternChar)) {
    
                        if (!inverseMap.containsKey(tentativeMatchString)) { // new pattern needed
                            map.put(patternChar, tentativeMatchString);
                            inverseMap.put(tentativeMatchString, patternChar);
    
                            if (dfs(pattern, pattenIndex + 1, str, i + 1, map, inverseMap)) {
                                return true;
                            }
    
                            map.remove(patternChar); // @note: need to remove, since this attempt is failed
                            inverseMap.remove(tentativeMatchString);
                        }
                    }
                }
                return false;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/word-pattern-ii/
    // Time: O(PS)
    // Space: O(S)
    class Solution {
    public:
        bool wordPatternMatch(string p, string s) {
            unordered_map<char, string> m;
            unordered_set<string> seen;
            function<bool(int,int)> dfs = [&](int i, int j) {
                if (i == p.size()) return j == s.size();
                if (m.count(p[i])) {
                    auto t = m[p[i]];
                    return s.substr(j, t.size()) == t && dfs(i + 1, j + t.size());
                } else {
                    string t;
                    for (int k = j; k < s.size(); ++k) {
                        t += s[k];
                        if (seen.count(t)) continue;
                        seen.insert(t);
                        m[p[i]] = t;
                        if (dfs(i + 1, k + 1)) return true;
                        seen.erase(t);
                        m.erase(p[i]);
                    }
                }
                return false;
            };
            return dfs(0, 0);
        }
    };
    
  • class Solution(object):
      def wordPatternMatch(self, pattern, str):
        """
        :type pattern: str
        :type str: str
        :rtype: bool
        """
    
        def dfs(p, s, pathp, paths, visited):
          if len(p) == len(s) == 0:
            return True
          if len(p) == 0 or len(p) > len(s):
            return False
          for i in range(0, len(s)):
            pathp.append(p[0])
            paths.append(s[:i + 1])
            if len(pathp) == len(paths) and len(set(paths)) == len(set(pathp)) == len(set(zip(paths, pathp))):
              if dfs(p[1:], s[i + 1:], pathp, paths, visited):
                return True
            pathp.pop()
            paths.pop()
          return False
    
        return dfs(pattern, str, [], [], {})
    
    

All Problems

All Solutions