題目

給定一種規律 pattern 和一個字符串 str ，判斷 str 是否遵循相同的規律。 這里的 遵循 指完全匹配，例如， pattern 里的每個字母和字符串 str 中的每個非空單詞之間存在著雙向連接的對應規律。

示例1:
輸入: pattern = “abba”, str = “dog cat cat dog”
輸出: true
示例 2:
輸入:pattern = “abba”, str = “dog cat cat fish”
輸出: false
示例 3:
輸入: pattern = “aaaa”, str = “dog cat cat dog”
輸出: false
示例 4:
輸入: pattern = “abba”, str = “dog dog dog dog”
輸出: false

說明:
你可以假設 pattern 只包含小寫字母， str 包含了由單個空格分隔的小寫字母。

解題思路

使用map數據結構，對出現的單詞和對應的字母進行映射。
對于任何一個單詞，分為兩種情況處理。

第一種情況：如果之前出現過，就要看它已經存在的映射字母，是否和現在待判斷的一致。如果一致，則映射還是正確的；如果不一致，說明單詞和模式不匹配。
這種情況的舉例如下：“dog dog cat dog” 和"aabc" 對于單詞dog，我們看第三個dog，它已存在的映射字母是a，此時待判斷的對應字母是c，發現a ≠c，所以不匹配。

第二種情況：單詞之前沒有出現過。我們要看當前的對應字符是否使用過。如果使用過，說明不匹配；如果沒使用過，就進行map映射。

詳細代碼注釋請參閱下面的測試代碼。

Leetcode代碼

class Solution { public:bool wordPattern(string pattern, string str) {map<string,char> word_letter;char used[128]={0};//已被映射的pattern字符string word;int pos=0;//當前指向的pattern字符str.push_back(' ');for(int i=0;i<str.length();i++){//cout<<str[i];if(str[i]==' '){if(word_letter.find(word)==word_letter.end())//沒有形成對應 {if(used[pattern[pos]]==1)//卻被標記 return false;//當前pattern字符已使用word_letter[word]=pattern[pos]; //cout<<word_letter[word]<<endl; used[pattern[pos]]=1;}else{//已經映射 if(word_letter[word]!=pattern[pos])//但是和已經存在的映射不匹配 return false;// cout<<word_letter[word]<<endl; }word="";pos++;//后移 }else{word+=str[i];}}//for(map<string,char>::iterator it=word_letter.begin();it!=word_letter.end();it++)//cout<<it->first<<" "<<it->second<<endl;if(pos!=pattern.length()) return false;//單詞個數和字符個數不一致 return true; } };

測試代碼

#include<iostream> #include<string> #include<map>using namespace std;bool wordPattern(string pattern,string str) {map<string,char> word_letter;char used[128]={0};//已被映射的pattern字符string word;//臨時保存拆分出來的單詞int pos=0;//當前指向的pattern字符 str.push_back(' ');//單詞最后加一個空格，便于處理//遍歷單詞strfor(int i=0;i<str.length();i++){//如果是空格，則知道前面是單詞if(str[i]==' '){if(word_letter.find(word)==word_letter.end())//沒有形成對應 {if(used[pattern[pos]]==1)//卻被標記 return false;//當前pattern字符已使用word_letter[word]=pattern[pos]; //形成映射//cout<<word_letter[word]<<endl; used[pattern[pos]]=1;//字母標記為使用過}else{//已經映射 if(word_letter[word]!=pattern[pos])//但是和已經存在的映射不匹配 return false;// cout<<word_letter[word]<<endl; }word="";//word清空，便于下一次使用pos++;//后移 }//如果是單詞else{word+=str[i];//單詞直接放到word中}} //使用迭代器遍歷map數據結構 //打印映射的具體內容for(map<string,char>::iterator it=word_letter.begin();it!=word_letter.end();it++)cout<<it->first<<" "<<it->second<<endl;if(pos!=pattern.length()) return false;//單詞個數和字符個數不一致 return true; }int main() {string str="dog dog fish fish cat";string letter="bbaac";if(wordPattern(letter,str))cout<<"matched";else cout<<"not matched"; }

測試用例

string str=“dog dog fish fish cat”;
string letter=“bbaac”;

測試結果

題目來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/word-pattern

希望對你有幫助。

總結

以上是生活随笔為你收集整理的Leetcode290单词规律-map使用的全部內容，希望文章能夠幫你解決所遇到的問題。

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