文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

給你一種規律 pattern 和一個字符串 str，請你判斷 str 是否遵循其相同的規律。

這里我們指的是 完全遵循，例如 pattern 里的每個字母和字符串 str 中每個 非空 單詞之間，存在著雙向連接的對應規律。

示例1: 輸入: pattern = "abab", str = "redblueredblue" 輸出: true示例2: 輸入: pattern = "aaaa", str = "asdasdasdasd" 輸出: true示例3: 輸入: pattern = "aabb", str = "xyzabcxzyabc" 輸出: false提示： 你可以默認 pattern 和 str 都只會包含小寫字母。

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/word-pattern-ii
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

class Solution {unordered_map<char, string> m;unordered_map<string, char> str_char;bool match = false; public:bool wordPatternMatch(string pattern, string str) {dfs(pattern, str, 0, 0);return match;}void dfs(string& pattern, string& str, int i, int j){if((i < pattern.size() && j >= str.size())|| (i >= pattern.size() && j < str.size()) || match)return;if(i == pattern.size() && j == str.size()){match = true;return;}if(!m.count(pattern[i])){string val;for(int k = 1; k <= str.size()-j; ++k)//該字符往后匹配多少個字符{val = str.substr(j, k);if(str_char.count(val) && str_char[val] != pattern[i])//"ab"，"aa"continue;m[pattern[i]] = val;str_char[val] = pattern[i];dfs(pattern, str, i+1, j+k);m.erase(pattern[i]);str_char.erase(val);}}else{string val = m[pattern[i]];int n = val.size();if(str.substr(j, n) != val)return;dfs(pattern, str, i+1, j+n);}} };

628 ms 52.5 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 291. 单词规律 II（回溯）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。