?LeetCode刷題實(shí)戰(zhàn)291：?jiǎn)卧~規(guī)律II
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.
給你一種規(guī)律 pattern 和一個(gè)字符串 str，請(qǐng)你判斷 str 是否遵循其相同的規(guī)律。
這里我們指的是 完全遵循，例如 pattern 里的每個(gè)字母和字符串 str 中每個(gè) 非空 單詞之間，存在著雙向連接的對(duì)應(yīng)規(guī)律。
示例
示例1:
輸入: pattern = "abab", str = "redblueredblue"
輸出: true
示例2:
輸入: pattern = "aaaa", str = "asdasdasdasd"
輸出: true
示例3:
輸入: pattern = "aabb", str = "xyzabcxzyabc"
輸出: false
提示：
你可以默認(rèn) pattern 和 str 都只會(huì)包含小寫(xiě)字母。
解題
class Solution {
public:
bool wordPatternMatch(string pattern, string str) {
unordered_map<char, string> m;
return helper(pattern, 0, str, 0, 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 + 1);
if (m.count(c) && m[c] == t) {
if (helper(pattern, p + 1, str, i + 1, 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 + 1, str, i + 1, m)) return true;
m.erase(c);
}
}
}
return false;
}
};