美文网首页算法
[每日一题]833. 字符串中的查找与替换

[每日一题]833. 字符串中的查找与替换

作者: 红树_ | 来源:发表于2023-08-14 11:48 被阅读0次

    题目

    LeetCode每日一题,参考833. 字符串中的查找与替换,难度分1461。

    解题思路

    • 排序+模拟:因为替换后会影响字符串下标的改变,先排序后按顺序替换并记录下一个开始的位置即可模拟替换过程。

    排序+模拟

    class Solution {
        public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
            //不重叠 直接按顺序替换
            int k = indices.length;
            //按照ids顺序访问indices就是下表从小到大开始替换
            Integer[] ids = new Integer[k];
            for(int i = 0; i < k; i++) ids[i] = i;
            Arrays.sort(ids,(a,b)->indices[a]-indices[b]);
            //按顺序替换
            StringBuilder ans = new StringBuilder();
            char[] cs = s.toCharArray();
            int pre = 0;//上次替换后结束下标
            for(int i = 0; i < k; i++) {
                int idx = ids[i], j = indices[idx]; //j访问下标
                //先把下标j前面不替换的放到结果ans里
                if(j > pre) ans.append(s.substring(pre,j));
                //判断是否要替换
                if(check(cs,sources[idx].toCharArray(),j)) {
                    ans.append(targets[idx]);
                    pre = j + sources[idx].length();
                }else {
                    pre = j;
                }
            }
            if(pre < s.length()) ans.append(s.substring(pre));
            return ans.toString();
        }
    
        boolean check(char[] s, char[] source, int pos){
            if(s.length < pos + source.length) return false;
            for(int i = 0; i < source.length; i++) {
                if(s[pos+i] != source[i]) return false;
            }
            return true;
        }
    }
    

    复杂度分析

    • 时间复杂度:O(k+klogk+n)k为尝试替换数组长度,排序klogkn为字符串长度。
    • 空间复杂度:O(k+logk),排序数组k,排序栈空间logk

    2023.08.15

    相关文章

      网友评论

        本文标题:[每日一题]833. 字符串中的查找与替换

        本文链接:https://www.haomeiwen.com/subject/cpxcmdtx.html