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

题目

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为尝试替换数组长度，排序klogk，n为字符串长度。
• 空间复杂度：O(k+logk)，排序数组k，排序栈空间logk。

2023.08.15