网站建设维护费合同范本,多用户购物商城,重庆企业网络推广网站,外贸SOHO建公司网站给你一种规律 pattern 和一个字符串 s#xff0c;请你判断 s 是否和 pattern 的规律相匹配。 如果存在单个字符到 非空 字符串的 双射映射 #xff0c;那么字符串 s 匹配 pattern #xff0c;即#xff1a;如果 pattern 中的每个字符都被它映射到的字符串替换#xff0c;那… 给你一种规律 pattern 和一个字符串 s请你判断 s 是否和 pattern 的规律相匹配。 如果存在单个字符到 非空 字符串的 双射映射 那么字符串 s 匹配 pattern 即如果 pattern 中的每个字符都被它映射到的字符串替换那么最终的字符串则为 s 。 双射 意味着映射双方一一对应不会存在两个字符映射到同一个字符串也不会存在一个字符分别映射到两个不同的字符串。 自己对一个题解的理解
我看的答案是如下这个代码我一开始不能理解 “为什么搜索结束后要把mymap[cur]还原为空后来示例pattern“abba”s “dogcatcatdog”进行了演示后知道了原因原因以注释的形式贴在了如下代码中
class Solution {
public:unordered_mapchar,string mymap;string all_pattern;bool dfs_search(int index, string s){// 结束条件if(index all_pattern.size()){if(s ) return true;else return false;}char cur all_pattern[index];if(mymap[cur] ! ){// 如果已经有映射,直接往下走// 6、由于“b“已经有映射了且mymap[b] o经过这个if判断会return false// 因此此时 s gcatcatdog “o” s.substr(0,1) gif(s.size() mymap[cur].size() mymap[cur] s.substr(0,mymap[cur].size()))return dfs_search(index1,s.substr(mymap[cur].size()));return false;}else {// 如果没有映射,开始探索string tmp_cur;// 0、当index 0s dogcatcatdog时此时哈希表为空还没有映射// 3、当index 1s ogcatcatdog时此时“b“还没有映射for(int i 0;is.size();i){// 1、令a映射到d即mymap[a] d// 4、令b映射到o即mymap[b] otmp_cur tmp_curs[i];mymap[cur] tmp_cur;// 确定不同字符映射 不会相同bool back1 true;for(auto each:mymap){if(each.first ! cur each.second tmp_cur){back1 false;break;}}if(back1 false) continue;// 确定后续使用正确// 2、dfs(1,ogcatcatdog)// 5、dfs(2,gcatcatdog)bool back2 dfs_search(index1,s.substr(mymap[cur].size()));// 7、back2 false说明后续错了进入下一个循环i 1// 8、进入下一个循环之后mymap[b] og,接着因为back2又是false// 又进入下一个循环mymap[b]会一直遍历到gcatcatdog都不发现不合适则// 退出循环也就是说没有找到mymap[b]的映射因此结束搜索if(back2 true) return true;}// 结束搜索一定要还原为空!// 因为找不到mymap[b]的映射所以 mymap[cur] // 9、 接下来则会回到上一层递归上一层递归是什么时候呢// 就是令a映射到d即mymap[a] d这个递归中i才等于0呢还可以去考虑// i1时使得 mymap[a] do的情况且因为“b”的映射重置了// 所以再去搜索“b”的映射过程同之前梳理的一样。mymap[cur] ;}return false;}bool wordPatternMatch(string pattern, string s) {all_pattern pattern;for(auto c:pattern){mymap[c] ;}return dfs_search(0,s);}
};
