栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

Leetcode——890.查找和替换模式

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

Leetcode——890.查找和替换模式

通过万岁!!!

  • 题目:给你一个字符串数组,然后给你一个模板,然后找到字符串数组中所有符合模板的字符串。这里的符合是指对应关系,例如模板是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;
    }
}
  • 总结:题目还是比较简单的,如果只是想单纯的通过的话。
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/970557.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号