Leetcode - 290. Word Patternアルゴリズム
7853 ワード
1.アルゴリズムの説明
一致するフォーマットが与えられ、文字列がフォーマットに合致するかどうかを判断します.単語文字列は、指定された一致フォーマットに完全に一致する必要があります.フォーマット文字列と単語文字列には二重放射関係があります.Example 1: Input: pattern = “abba”, str = “dog cat cat dog” Output: true
Example 2: Input:pattern = “abba”, str = “dog cat cat fish” Output: false
Example 3: Input: pattern = “aaaa”, str = “dog cat cat dog” Output: false
Example 4: Input: pattern = “abba”, str = “dog dog dog dog” Output: false
2.思想分析
(1)フォーマット文字列が回文である場合、単語文字列も回文フォーマットである必要がある.(2)単一重複文字列であれば、単語文字列のすべての単語も同様である.(3)すべてが異なる文字であれば、単語文字列はすべての単語が異なる;...
しかし、アルゴリズムはいつも状況ごとに処理することができず、法則を見つける必要がある:Step 1.単語文字列を分割し、vectorに格納します.Step 2. フォーマット文字列の各文字の位置をマークする2つのmapを用意します.Step 1 Vectorにおける単語の位置をマークするStep 3.位置情報を比較し、一致しない場合はreturn false.
3.参照コード
一致するフォーマットが与えられ、文字列がフォーマットに合致するかどうかを判断します.単語文字列は、指定された一致フォーマットに完全に一致する必要があります.フォーマット文字列と単語文字列には二重放射関係があります.Example 1: Input: pattern = “abba”, str = “dog cat cat dog” Output: true
Example 2: Input:pattern = “abba”, str = “dog cat cat fish” Output: false
Example 3: Input: pattern = “aaaa”, str = “dog cat cat dog” Output: false
Example 4: Input: pattern = “abba”, str = “dog dog dog dog” Output: false
2.思想分析
(1)フォーマット文字列が回文である場合、単語文字列も回文フォーマットである必要がある.(2)単一重複文字列であれば、単語文字列のすべての単語も同様である.(3)すべてが異なる文字であれば、単語文字列はすべての単語が異なる;...
しかし、アルゴリズムはいつも状況ごとに処理することができず、法則を見つける必要がある:Step 1.単語文字列を分割し、vectorに格納します.Step 2. フォーマット文字列の各文字の位置をマークする2つのmapを用意します.Step 1 Vectorにおける単語の位置をマークするStep 3.位置情報を比較し、一致しない場合はreturn false.
3.参照コード
class Solution {
public:
bool wordPattern(string pattern, string str) {
vector<string> vectStr;
string tmpStr;
map<char, vector<int>> mapPattern;
map<string, vector<int>> mapStr;
int i = 0;
for (i = 0; i < str.length(); i++)
{
if (str[i] == ' ')
{
vectStr.push_back(tmpStr);
tmpStr.clear();
}
else
{
tmpStr.push_back(str[i]);
}
if ( i == str.length() - 1) vectStr.push_back(tmpStr);
}
if (pattern.size() != vectStr.size()) return false;
for (i = 0; i < pattern.length(); i++)
{
mapPattern[pattern[i]].push_back(i);
mapStr[vectStr[i]].push_back(i);
if (mapPattern[pattern[i]] != mapStr[vectStr[i]]) return false;
}
return true;
}
};