Skip to content

291. Word Pattern II 👍

  • Time: $O(|\texttt{pattern}|^{|\texttt{s}|})$
  • Space: $O(|\texttt{pattern}|^{|\texttt{s}|})$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
 public:
  bool wordPatternMatch(string pattern, string s) {
    return isMatch(pattern, 0, s, 0, unordered_map<char, string>(),
                   unordered_set<string>());
  }

 private:
  bool isMatch(const string& pattern, int i, const string& s, int j,
               unordered_map<char, string>&& charToString,
               unordered_set<string>&& seen) {
    if (i == pattern.length() && j == s.length())
      return true;
    if (i == pattern.length() || j == s.length())
      return false;

    const char c = pattern[i];

    if (const auto it = charToString.find(c); it != charToString.cend()) {
      const string& t = it->second;
      // Check if we can match t w/ s[j:]
      if (s.substr(j).find(t) == string::npos)
        return false;

      // If can match, so continue match the rest
      return isMatch(pattern, i + 1, s, j + t.length(), move(charToString),
                     move(seen));
    }

    for (int k = j; k < s.length(); ++k) {
      const string& t = s.substr(j, k - j + 1);

      // This string is already mapped by other character
      if (seen.count(t))
        continue;

      charToString[c] = t;
      seen.insert(t);

      if (isMatch(pattern, i + 1, s, k + 1, move(charToString), move(seen)))
        return true;

      // Backtracking
      charToString.erase(c);
      seen.erase(t);
    }

    return false;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
  public boolean wordPatternMatch(String pattern, String s) {
    return isMatch(pattern, 0, s, 0, new HashMap<>(), new HashSet<>());
  }

  private boolean isMatch(final String pattern, int i, final String s, int j,
                          Map<Character, String> charToString, Set<String> seen) {
    if (i == pattern.length() && j == s.length())
      return true;
    if (i == pattern.length() || j == s.length())
      return false;

    final char c = pattern.charAt(i);

    if (charToString.containsKey(c)) {
      final String t = charToString.get(c);
      // Check if we can match t w/ s[j:]
      if (!s.startsWith(t, j))
        return false;

      // If can match, so continue match the rest
      return isMatch(pattern, i + 1, s, j + t.length(), charToString, seen);
    }

    for (int k = j; k < s.length(); ++k) {
      final String t = s.substring(j, k + 1);

      // This string is already mapped by other character
      if (seen.contains(t))
        continue;

      charToString.put(c, t);
      seen.add(t);

      if (isMatch(pattern, i + 1, s, k + 1, charToString, seen))
        return true;

      // Backtracking
      charToString.remove(c);
      seen.remove(t);
    }

    return false;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution:
  def wordPatternMatch(self, pattern: str, s: str) -> bool:
    def isMatch(i: int, j: int, charToString: Dict[chr, str], seen: Set[str]) -> bool:
      if i == len(pattern) and j == len(s):
        return True
      if i == len(pattern) or j == len(s):
        return False

      c = pattern[i]

      if c in charToString:
        t = charToString[c]
        # Check if we can match t w// s[j..j + len(t))
        if t not in s[j:]:
          return False

        # If can match, so continue match the rest
        return isMatch(i + 1, j + len(t), charToString, seen)

      for k in range(j, len(s)):
        t = s[j:k + 1]

        # This is already mapped by other character
        if t in seen:
          continue

        charToString[c] = t
        seen.add(t)

        if isMatch(i + 1, k + 1, charToString, seen):
          return True

        # Backtracking
        del charToString[c]
        seen.remove(t)

      return False

    return isMatch(0, 0, {}, set())