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

• Java
• C++
• Python

• 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