Given a pattern and a string str, find if strfollows 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.
Example 1:
Input: pattern ="abab", str ="redblueredblue"
Output: true
Example 2:
Input: pattern = pattern ="aaaa", str ="asdasdasdasd"
Output: true
Example 3:
Input: pattern ="aabb", str ="xyzabcxzyabc"
Output: false
Notes:
You may assume both pattern and str contains only lowercase letters.
这道题是之前那道 Word Pattern 的拓展，之前那道题词语之间都有空格隔开，这样可以一个单词一个单词的读入，然后来判断是否符合给定的特征，而这道题没有空格了，那么难度就大大的增加了，因为我们不知道对应的单词是什么，所以得自行分开，可以用回溯法来生成每一种情况来判断，这里还是需要用 HashMap 来建立模式字符和单词之间的映射，还需要用变量p和r来记录当前递归到的模式字符和单词串的位置，在递归函数中，如果p和r分别等于模式字符串和单词字符串的长度，说明此时匹配成功结束了，返回 ture，反之如果一个达到了而另一个没有，说明匹配失败了，返回 false。如果都不满足上述条件的话，取出当前位置的模式字符，然后从单词串的r位置开始往后遍历，每次取出一个单词，如果模式字符已经存在 HashMap 中，而且对应的单词和取出的单词也相等，那么再次调用递归函数在下一个位置，如果返回 true，那么就返回 true。反之如果该模式字符不在 HashMap 中，要看有没有别的模式字符已经映射了当前取出的单词，如果没有的话，建立新的映射，并且调用递归函数，注意如果递归函数返回 false 了，要在 HashMap 中删去这个映射，参见代码如下：
解法一：
class Solution {
public:
bool wordPatternMatch(string pattern, string str) {
unordered_map<char, string> m;
return helper(pattern, , str, , m);
}
bool helper(string pattern, int p, string str, int r, unordered_map<char, string> &m) {
if (p == pattern.size() && r == str.size()) return true;
if (p == pattern.size() || r == str.size()) return false;
char c = pattern[p];
for (int i = r; i < str.size(); ++i) {
string t = str.substr(r, i - r + );
if (m.count(c) && m[c] == t) {
if (helper(pattern, p + , str, i + , m)) return true;
} else if (!m.count(c)) {
bool b = false;
for (auto it : m) {
if (it.second == t) b = true;
}
if (!b) {
m[c] = t;
if (helper(pattern, p + , str, i + , m)) return true;
m.erase(c);
}
}
}
return false;
}
};
下面这种方法和上面那种方法很类似，不同点在于使用了 set，而使用其的原因也是为了记录所有和模式字符建立过映射的单词，这样就不用每次遍历 HashMap 了，只要在 set 中查找取出的单词是否存在，如果存在了则跳过后面的处理，反之则进行和上面相同的处理，注意还要在 set 中插入新的单词，最后也要同时删除掉，参见代码如下：
解法二：
class Solution {
public:
bool wordPatternMatch(string pattern, string str) {
unordered_map<char, string> m;
unordered_set<string> st;
return helper(pattern, , str, , m, st);
}
bool helper(string pattern, int p, string str, int r, unordered_map<char, string> &m, unordered_set<string> &st) {
if (p == pattern.size() && r == str.size()) return true;
if (p == pattern.size() || r == str.size()) return false;
char c = pattern[p];
for (int i = r; i < str.size(); ++i) {
string t = str.substr(r, i - r + );
if (m.count(c) && m[c] == t) {
if (helper(pattern, p + , str, i + , m, st)) return true;
} else if (!m.count(c)) {
if (st.count(t)) continue;
m[c] = t;
st.insert(t);
if (helper(pattern, p + , str, i + , m, st)) return true;
m.erase(c);
st.erase(t);
}
}
return false;
}
};
再来看一种不写 helper 函数的解法，可以调用自身，思路和上面的方法完全相同，参见代码如下：
解法三：
class Solution {
public:
bool wordPatternMatch(string pattern, string str) {
if (pattern.empty()) return str.empty();
if (m.count(pattern[])) {
string t = m[pattern[]];
if (t.size() > str.size() || str.substr(, t.size()) != t) return false;
if (wordPatternMatch(pattern.substr(), str.substr(t.size()))) return true;
} else {
for (int i = ; i <= str.size(); ++i) {
if (st.count(str.substr(, i))) continue;
m[pattern[]] = str.substr(, i);
st.insert(str.substr(, i));
if (wordPatternMatch(pattern.substr(), str.substr(i))) return true;
m.erase(pattern[]);
st.erase(str.substr(, i));
}
}
return false;
}
unordered_map<char, string> m;
unordered_set<string> st;
};
Github 同步地址：
https://github.com/grandyang/leetcode/issues/291
类似题目：
参考资料：
https://leetcode.com/problems/word-pattern-ii/
https://leetcode.com/problems/word-pattern-ii/discuss/73721/My-simplified-java-version
https://leetcode.com/problems/word-pattern-ii/discuss/73664/Share-my-Java-backtracking-solution