LeetCode第890题,难度中等。
原题地址:https://leetcode-cn.com/problems/find-and-replace-pattern/
题目描述:
你有一个单词列表 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 映射到同一个字母。
提示:
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-and-replace-pattern
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路:
这题我采用了我认知中的最粗暴的方式,就是遍历每个word,设定两个Map,分别表示word和pattern的相互之间的映射关系。
遍历pattern中的每个p和word中的每个w,从两个Map中获取到w和p对应的p和w,如果不相同,则表示两个不匹配;否则表示该p和w匹配上了,继续下一个p和w的匹配。
最后,将所有完全匹配的字符串添加到List结果集中返回。
中文官网题解:
https://leetcode-cn.com/problems/find-and-replace-pattern/solution/
个人题解:
class Solution {
public List<String> findAndReplacePattern(String[] words, String pattern) {
List<String> list = new ArrayList<>(words.length);
char[] patterns = pattern.toCharArray();
for (String word : words) {
Map<Character, Character> map = new HashMap<>(word.length());
Map<Character, Character> rmap = new HashMap<>(word.length());
boolean flag = false;
for (int i = 0; i < pattern.length(); i++) {
char p = patterns[i];
char w = word.charAt(i);
Character pp = rmap.get(w);
Character ww = map.get(p);
if (pp == null && ww == null) {
map.put(p, w);
rmap.put(w, p);
}
if ((ww != null && ww != w) || (pp != null && pp != p)) {
flag = true;
break;
}
}
if (!flag) {
list.add(word);
}
}
return list;
}
}
结果:
虽然很快,但不是最快,还需努力啊。