通过万岁!!!
- 题目:给你一个字符串数组,然后给你一个模板,然后找到字符串数组中所有符合模板的字符串。这里的符合是指对应关系,例如模板是ABB模式,则选出的字符串也必须是ABB模式的。
- 思路:首先就是处理模板,这里我处理成了map,每一个字符都作为map的key,value是这个字符在模板中的下标。然后针对每一个字符串,我们都对这个map进行遍历,看一下是不是符合。下面对一个字符串word的遍历过程进行分析,首先是我们要遍历map,每次拿到map的一组value(其实是一个list,表示的是这个key在模板中出现的位置的下标),我们就对其进行遍历,只不过遍历之前,先确定这个key对应的word中的字符是什么。也就是先拿到list的第一个位置的在word中对应的字符,我们假设为c,那么这个c一定是之前我们没有查找过的,因为c就对应map中当前的这key,是一一对应的。我们第一个遍历这个key,那么c也一定是第一次出现的,如果出现过(用一个set进行判断),则一定不满足,直接break。然后就是遍历这个list,保证list中的idx在word中对应的字符都是c。否则直接也是不满足模板的。
- 技巧:这里就是用到了哈希表,但是我的效率不是很高,只能说通过万岁了。
java代码
class Solution {
public List findAndReplacePattern(String[] words, String pattern) {
List ans = new ArrayList<>();
Map> map = new HashMap<>();
int patternLen = pattern.length();
for (int i = 0; i < patternLen; i++) {
map.putIfAbsent(pattern.charAt(i), new ArrayList<>());
map.get(pattern.charAt(i)).add(i);
}
boolean flag;
Set set;
for (int i = 0; i < words.length; i++) {
if (words[i].length() != patternLen) {
continue;
}
set = new HashSet<>();
flag = true;
for (Map.Entry> e : map.entrySet()) {// 遍历map
if (!flag) {
break;
}
List list = e.getValue();
char c = words[i].charAt(list.get(0));// 当前这个字符对应的
if (set.contains(c)) {// 这个字符之前已经被对应过
flag = false;
break;
}
set.add(c);
for (Integer idx : list) {// 遍历list
if (words[i].charAt(idx) != c) {
flag = false;
break;
}
}
}
if (!flag) {
continue;
} else {
ans.add(words[i]);
}
}
return ans;
}
}
- 总结:题目还是比较简单的,如果只是想单纯的通过的话。



