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

【题解】Leetcode 双周赛80 替换字符后匹配

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

【题解】Leetcode 双周赛80 替换字符后匹配

替换字符后匹配

题目来源:Leetcode双周赛80

标签:字符串匹配、哈希

给你两个字符串 s 和 sub 。同时给你一个二维字符数组 mappings ,其中 m a p p i n g s [ i ] = [ o l d i , n e w i ] mappings[i] = [old_i, new_i] mappings[i]=[oldi​,newi​] 表示你可以替换 sub 中任意数目的 o l d i old_i oldi​ 个字符,替换成 n e w i new_i newi​ 。sub 中每个字符 不能 被替换超过一次。

如果使用 mappings 替换 0 个或者若干个字符,可以将 sub 变成 s 的一个子字符串,请你返回 true,否则返回 false 。

一个 子字符串 是字符串中连续非空的字符序列。

输入:s = "fool3e7bar", sub = "leet", mappings = [["e","3"],["t","7"],["t","8"]]
输出:true

开始的思路——暴力模拟:

感觉思路是对的,但是就是不能完全通过…

出个小考验:哪位兄弟有能找出来Bug?

class Solution {
    Map> m = new HashMap<>();
    public boolean matchReplacement(String s, String sub, char[][] mappings) {
        int n = mappings.length;
        for (int i = 0;i < n;i++){
            Set set = m.getOrDefault(mappings[i][0],new HashSet<>());
            set.add(mappings[i][1]);
            m.put(mappings[i][0],set);
        }
        int idx1 = 0,idx2 = 0;
        int len1 = s.length(),len2 = sub.length();
        while (idx1 < len1 && idx2 < len2){
            char a = s.charAt(idx1), b = sub.charAt(idx2);
            if (a == b){
                idx1 += 1;
                idx2 += 1;
            }else if (m.get(b) == null){
                idx1 += 1;
                idx2 = 0;
            }else{
                Set set = m.get(b);
                if (set.contains(a)){
                    idx2 += 1;
                }else{
                    idx2 = 0;
                }
                idx1 += 1;
            }
        }
        return idx2 == len2;
    }
}

修改了下:

将一个可替换映射对应成一个整数,然后依然是暴力匹配

class Solution {
    public boolean matchReplacement(String s, String sub, char[][] mappings) {
        Set hash = new HashSet<>();
        for (char [] v : mappings){
            hash.add(v[0] * 256 + v[1]); // 一个转换对应于一个唯一的整数
        }
        int n = s.length(), m = sub.length();
        for (int i = 0;i < n - m + 1;i++){
            boolean flag = true; // 默认能匹配
            for (int j = 0;j < m;j++){
                if (s.charAt(i+j) != sub.charAt(j) && !hash.contains(sub.charAt(j) * 256 + s.charAt(i+j))){
                    flag = false;
                    break;
                }
            }
            if (flag) return true;
        }
        return false;
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/970065.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

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

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