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 <= 20pattern and s consist of only lowercase English letters.
Solutions
Solution 1
PythonJavaC++Go
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)(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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)
}(code-box)
