【LeetCode-290】Word Pattern(C++)
タイトルの要件:
パターン文字列patternとstring文字列strの2つの文字列をあげます.str文字列がpattern文字列で表されるパターンに合致するか否かを判断する.例:
パターン文字列patternとstring文字列strの2つの文字列をあげます.str文字列がpattern文字列で表されるパターンに合致するか否かを判断する.例:
pattern = "abba"
、str="dog cat cat dog"
はtrueを します.
pattern="abba"
、str="dog cat cat fish"
はfalseを します.
pattern="aaaa"
、str="dog cat cat dog"
はfalseを します.
pattern="abba"
、str="dog dog dog dog"
はfalseを します.
:patterとstrの はすべて で、str はいくつかのスペースで られた だと できます.
の え :
str がpattern のパターンに するかどうかを するには、まずstr を します.すなわち、「dog cat cat dog」のような い を「dog」、「cat」、「cat」、「dog」のような4つの い に します.これで できます.プログラムには、 された をvectorコンテナで します.stringタイプのwordを して を します.str をforループで し、スペース に すると、wordに されている をvectorに し、wordを の に しくします.
は のとおりです.
vector<string> sstr;
string word("");
for(int i = 0;i< str.length();i++){
if(str[i]==' '){
sstr.push_back(word);
word="";
}
else
word+=str[i];
if(i==str.length()-1)
sstr.push_back(word);
}
に、mpがpattern[i]のcharをキー とし、msがsstr[i]のstringをキー とする2つの mapを する. にmpとmsを する でパターンに するか かを する.プログラム :class Solution {
public:
bool wordPattern(string pattern,string str)
{
vector<string> sstr;
string word("");
for(int i = 0;i< str.length();i++){
if(str[i]==' '){
sstr.push_back(word);
word="";
}
else
word+=str[i];
if(i==str.length()-1)
sstr.push_back(word);
}
if(pattern.length()!=sstr.size()){
return false;
}// pattern sstr , str pattern。
unordered_map<char,string>mp;
unordered_map<string,char>ms;
for(int i=0;i<pattern.length();i++){
if(mp.find(pattern[i])==mp.end()&&ms.find(sstr[i])==ms.end()){
mp[pattern[i]]=sstr[i];
ms[sstr[i]]==pattern[i];
}// mp ms , mp pattern[i], ms sstr[i], , mp ms 。
else if(mp.find(pattern[i])!=mp.end()&&ms.find(sstr[i])!=ms.end()){
if(mp[pattern[i]]!=sstr[i])
return false;
}// mp pattern[i], ms sstr[i], ( “aba” “dog cat cat”, i=2 // a mp ,
//cat ms , a dog, ), false。
else return false;// , mp ,ms , ms ,mp 。 . }
return true;
}
};
まとめ:
mapとsetを したいと っていました.カットされた をsetで し、mapで を します(charをキー とします).これで1つのmapを なく できますが、 えてみるとsetはfindの を たすことができますが、ランダムにアクセスできません. の の はかなり くなり、いくつかのエラーに してもすぐに を つけることができます.