Question

291. Word Pattern II

中文文档

Description

Given a pattern and a string s, return true_ if _s_ matches the _pattern_._

A string s matches a pattern if there is some bijective mapping of single characters to non-empty strings such that if each character in pattern is replaced by the string it maps to, then the resulting string is s. A bijective mapping means that no two characters map to the same string, and no character maps to two different strings.

 

Example 1:

Input: pattern = "abab", s = "redblueredblue"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "red"
'b' -> "blue"

Example 2:

Input: pattern = "aaaa", s = "asdasdasdasd"
Output: true
Explanation: One possible mapping is as follows:
'a' -> "asd"

Example 3:

Input: pattern = "aabb", s = "xyzabcxzyabc"
Output: false

 

Constraints:

• 1 <= pattern.length, s.length <= 20
• pattern and s consist of only lowercase English letters.

Solutions

Solution 1

class Solution:
  def wordPatternMatch(self, pattern: str, s: str) -> bool:
    def dfs(i, j):
      if i == m and j == n:
        return True
      if i == m or j == n or n - j < m - i:
        return False
      for k in range(j, n):
        t = s[j : k + 1]
        if d.get(pattern[i]) == t:
          if dfs(i + 1, k + 1):
            return True
        if pattern[i] not in d and t not in vis:
          d[pattern[i]] = t
          vis.add(t)
          if dfs(i + 1, k + 1):
            return True
          d.pop(pattern[i])
          vis.remove(t)
      return False

    m, n = len(pattern), len(s)
    d = {}
    vis = set()
    return dfs(0, 0)

class Solution {
  private Set<String> vis;
  private Map<Character, String> d;
  private String p;
  private String s;
  private int m;
  private int n;

  public boolean wordPatternMatch(String pattern, String s) {
    vis = new HashSet<>();
    d = new HashMap<>();
    this.p = pattern;
    this.s = s;
    m = p.length();
    n = s.length();
    return dfs(0, 0);
  }

  private boolean dfs(int i, int j) {
    if (i == m && j == n) {
      return true;
    }
    if (i == m || j == n || m - i > n - j) {
      return false;
    }
    char c = p.charAt(i);
    for (int k = j + 1; k <= n; ++k) {
      String t = s.substring(j, k);
      if (d.getOrDefault(c, "").equals(t)) {
        if (dfs(i + 1, k)) {
          return true;
        }
      }
      if (!d.containsKey(c) && !vis.contains(t)) {
        d.put(c, t);
        vis.add(t);
        if (dfs(i + 1, k)) {
          return true;
        }
        vis.remove(t);
        d.remove(c);
      }
    }
    return false;
  }
}

class Solution {
public:
  bool wordPatternMatch(string pattern, string s) {
    unordered_set<string> vis;
    unordered_map<char, string> d;
    return dfs(0, 0, pattern, s, vis, d);
  }

  bool dfs(int i, int j, string& p, string& s, unordered_set<string>& vis, unordered_map<char, string>& d) {
    int m = p.size(), n = s.size();
    if (i == m && j == n) return true;
    if (i == m || j == n || m - i > n - j) return false;
    char c = p[i];
    for (int k = j + 1; k <= n; ++k) {
      string t = s.substr(j, k - j);
      if (d.count(c) && d[c] == t) {
        if (dfs(i + 1, k, p, s, vis, d)) return true;
      }
      if (!d.count(c) && !vis.count(t)) {
        d[c] = t;
        vis.insert(t);
        if (dfs(i + 1, k, p, s, vis, d)) return true;
        vis.erase(t);
        d.erase(c);
      }
    }
    return false;
  }
};

func wordPatternMatch(pattern string, s string) bool {
  m, n := len(pattern), len(s)
  vis := map[string]bool{}
  d := map[byte]string{}
  var dfs func(i, j int) bool
  dfs = func(i, j int) bool {
    if i == m && j == n {
      return true
    }
    if i == m || j == n || m-i > n-j {
      return false
    }
    c := pattern[i]
    for k := j + 1; k <= n; k++ {
      t := s[j:k]
      if v, ok := d[c]; ok && v == t {
        if dfs(i+1, k) {
          return true
        }
      }
      if _, ok := d[c]; !ok && !vis[t] {
        d[c] = t
        vis[t] = true
        if dfs(i+1, k) {
          return true
        }
        delete(d, c)
        vis[t] = false
      }
    }
    return false
  }
  return dfs(0, 0)
}