題目:
你有一個(gè)單詞列表 words 和一個(gè)模式 pattern拱烁,你想知道 words 中的哪些單詞與模式匹配慨蛙。
如果存在字母的排列 p ,使得將模式中的每個(gè)字母 x 替換為 p(x) 之后榕茧,我們就得到了所需的單詞扛禽,那么單詞與模式是匹配的。
(回想一下侈净,字母的排列是從字母到字母的雙射:每個(gè)字母映射到另一個(gè)字母尊勿,沒有兩個(gè)字母映射到同一個(gè)字母。)
返回 words 中與給定模式匹配的單詞列表畜侦。
你可以按任何順序返回答案运怖。
示例:
輸入:words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
輸出:["mee","aqq"]
解釋:
"mee" 與模式匹配,因?yàn)榇嬖谂帕?{a -> m, b -> e, ...}夏伊。
"ccc" 與模式不匹配摇展,因?yàn)?{a -> c, b -> c, ...} 不是排列。
因?yàn)?a 和 b 映射到同一個(gè)字母溺忧。
解題方法:
這道題有點(diǎn)像正則化匹配咏连,就是找words里面符合pattern特點(diǎn)的字符串。但是怎么判斷說實(shí)話我自己做還是挺蒙的鲁森,這里搬運(yùn)一下題解中的優(yōu)秀方法:
利用string的find函數(shù)判斷兩個(gè)字符串相同位置的字母是否在字符串中出現(xiàn)的狀態(tài)(位置)相同祟滴。
代碼和結(jié)果:
class Solution {
public:
bool compare(string word,string pattern)
{
if(word.size()!=pattern.size()) return false;
else
{
for(int i=0;i<word.size();i++)
{
if(word.find(word[i])!=pattern.find(pattern[i]))
return false;
}
return true;
}
}
vector<string> findAndReplacePattern(vector<string>& words, string pattern) {
vector<string> res;
for(int i=0;i<words.size();i++)
{
if(compare(words[i],pattern))
res.push_back(words[i]);
}
return res;
}
};
運(yùn)行結(jié)果:最近逐漸忙起來了,刷題的難題也上來了歌溉,總的來說就是有點(diǎn)累垄懂。
原題鏈接:https://leetcode-cn.com/problems/find-and-replace-pattern/