題目描述：

給定一種規律 pattern 和一個字符串 s ，判斷 s 是否遵循相同的規律。

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

輸入輸出樣例：

示例 1：
輸入：pattern = “abba”, s = “dog cat cat dog”
輸出：true

示例 2：
輸入：pattern = “abba”, s = “dog cat cat fish”
輸出：false

示例 3：
輸入：pattern = “aaaa”, s = “dog cat cat dog”
輸出：false

提示：
1 <= pattern.length <= 300
pattern 只包含小寫英文字母
1 <= s.length <= 3000
s 只包含小寫英文字母和 ’ ’
s 不包含 任何前導或尾隨對空格
s 中每個單詞都被 單個空格 分隔

題解：

解題思路：

思路一（哈希表）：

1、具體思路如下：
判斷 pattern 中的字符c 與 s中對應的字符串 str 是否對應。
①、c 之前存在映射關系
????????之前的映射關系與 c:str 相同，繼續判斷pattern中剩余字符
????????之前的映射袁旭與 c:str 不同，返回false
②、c 之前不存在映射關系
????????str 不存在之前的映射關系中，建立映射關系 c:str
????????str 存在之前的映射關系中，返回false
2、復雜度分析：
① 時間復雜度：O(n + m)，其中n是字符串s的長度，m是pattern的長度。在循環中使用ss >> str因此整個字符串的處理是O(n)，遍歷pattern中的每個字符進行匹配O(m)。
② 空間復雜度：O(n + m)，stringstream的消耗和需要存儲pattern中的字符映射和s中的單詞。

代碼實現

代碼實現（思路一（哈希表））：

class Solution {
public:bool wordPattern(string pattern, string s) {stringstream ss(s);  // 使用stringstream將輸入字符串s分割成單詞unordered_map<char, string> mp;  // 用于存儲字符和單詞的映射關系unordered_set<string> set;  // 用于檢查一個單詞是否已經被映射string str;for (int i = 0; i < pattern.size(); i++) {  // 遍歷pattern中的每個字符ss >> str;  // 從stringstream中讀取一個單詞if (mp.count(pattern[i])) {  // 如果當前字符已經有映射if (mp[pattern[i]] != str) {  // 檢查當前字符映射的單詞是否與當前單詞相同return false;  // 如果不同，則返回false}} else {if (set.count(str)) {  // 如果當前單詞已經被其他字符映射過return false;  // 如果是重復的單詞，返回false}mp[pattern[i]] = str;  // 為當前字符創建一個新的映射關系set.insert(str);  // 將當前單詞添加到set中，確保它不會被重復映射}}if (ss >> str) return false;  // 如果在讀取完所有pattern字符后仍有剩余的單詞，則返回false，表示長度不匹配return true;  // 如果所有檢查都通過，返回true}
};

以思路一為例進行調試

#include<iostream>
#include<unordered_map>
#include<unordered_set>
#include<sstream>
using namespace std;class Solution {
public:bool wordPattern(string pattern, string s) {stringstream ss(s);  // 使用stringstream將輸入字符串s分割成單詞unordered_map<char, string> mp;  // 用于存儲字符和單詞的映射關系unordered_set<string> set;  // 用于檢查一個單詞是否已經被映射string str;for (int i = 0; i < pattern.size(); i++) {  // 遍歷pattern中的每個字符ss >> str;  // 從stringstream中讀取一個單詞if (mp.count(pattern[i])) {  // 如果當前字符已經有映射if (mp[pattern[i]] != str) {  // 檢查當前字符映射的單詞是否與當前單詞相同return false;  // 如果不同，則返回false}} else {if (set.count(str)) {  // 如果當前單詞已經被其他字符映射過return false;  // 如果是重復的單詞，返回false}mp[pattern[i]] = str;  // 為當前字符創建一個新的映射關系set.insert(str);  // 將當前單詞添加到set中，確保它不會被重復映射}}if (ss >> str) return false;  // 如果在讀取完所有pattern字符后仍有剩余的單詞，則返回false，表示長度不匹配return true;  // 如果所有檢查都通過，返回true}
};int main(int argc, char const *argv[])
{string pattern="abba";string s="dog dog dog dog";Solution s1;if (s1.wordPattern(pattern,s)){cout<<"true"<<endl;    }else{cout<<"false"<<endl;}return 0;
}

LeetCode 面試經典 150_哈希表_單詞規律（41_290)原題鏈接
歡迎大家和我溝通交流(????)