LintCode-829. Word Pattern II (DFS难题）

这题挺难的，我也是参考的网上的解法，这个解法可以算是一种DFS暴力遍历所有可能解把。
注意 ：
1）在helper()里面，如果调用的helper()返回false，不能直接返回false，而是要继续处理其他的solution。注意这个跟其他返回vector< vector<> >的情况不一样，因为这里只是返回true/false。
2) map和set没有pop_back()操作，只能用erase。

class Solution {
public:/*** @param pattern: a string,denote pattern string* @param str: a string, denote matching string* @return: a boolean*/bool wordPatternMatch(string &pattern, string &str) {map<char, string> m;set<string> s;return helper(pattern, str, m, s);}private:bool beginWith(string const &str, string const &subStr) {if (subStr.size() > str.size()) return false;if (subStr == str.substr(0, subStr.size())) return true;return false;}bool helper(string pat, string str, map<char, string> &m, set<string> &s) {if (pat.size() == 0)return str.size() == 0;char c = pat[0];if (m.find(c) != m.end()) { //如果c已经存在，则看str是不是以c对应字符串开头if (beginWith(str, m[c])) {return helper(pat.substr(1), str.substr(m[c].size()), m, s);}return false;}//如果pat[0]是一个新的char, 则要试探性的把str[0], str[0..1], ..., str[0..n]跟pat[0]匹配//这里要用到set，表示这个str[]已经被用for (int i = 0; i < str.size(); ++i) {string subWord = str.substr(0, i + 1);if (s.find(subWord) == s.end()) { //如果subWord是新的s.insert(subWord);m[c] = subWord; //也可以m.insert(make_pair(c, subWord));//注意：这里不能简单return，因为如果helper()是false, 其他solution仍然可能对//return helper(pat.substr(1), str.substr(i + 1), m, s);if (helper(pat.substr(1), str.substr(i + 1), m, s))return true;s.erase(subWord);     //set和map没有pop_back()操作！！！m.erase(c);}    }return false;}
};

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！