题目描述
你有一个单词列表 $words$ 和一个模式 $pattern$,你想知道 $words$ 中的哪些单词与模式匹配。
如果存在字母的排列 $p$ ,使得将模式中的每个字母 $x$ 替换为 $p(x)$ 之后,我们就得到了所需的单词,那么单词与模式是匹配的。
(回想一下,字母的排列是从字母到字母的双射:每个字母映射到另一个字母,没有两个字母映射到同一个字母。)
返回 $words$ 中与给定模式匹配的单词列表。
你可以按任何顺序返回答案。
示例:
输入:words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
输出:["mee","aqq"]
解释:
"mee" 与模式匹配,因为存在排列 {a -> m, b -> e, ...}。
"ccc" 与模式不匹配,因为 {a -> c, b -> c, ...} 不是排列。
因为 a 和 b 映射到同一个字母。
提示:
- $1 <= words.length <= 50$
- $1 <= pattern.length = words[i].length <= 20$
算法
对于每个字符串,记录其映射过程,使用一个32位的int记录那些字母已经被映射过了,不能再使用了
C++ 代码
class Solution {
public:
vector<string> findAndReplacePattern(vector<string>& words, string &pattern) {
char m[26]; //记录映射
vector<string> res;
for(auto &s : words)
{
memset(m, 0, sizeof m); // 初始化每个word 对 pattern 的映射
int use = 0, n = s.size(), i = 0; // use 目标那些字母已经被映射过了
while (i < n)
{
if (m[s[i] - 'a'] == '\0') { // 如果当前结点还未构造映射
if (use & (1 << (pattern[i] - 'a'))) break; // 如果将要映射的字母,已经被别的字母映射过了,即出错
m[s[i] - 'a'] = pattern[i]; // 完成映射
use |= (1 << pattern[i] - 'a'); // 完成对于被映射字母的 ,添加已使用的标记
}
else
{
if (m[s[i] - 'a'] != pattern[i]) break; // 当前结点的映射结点,不是目标结点 错配
}
i++;
}
if (i == n) res.emplace_back(s); //全程没出错时, 成功
}
return res;
}
};