【LeetCode 算法】Find And Replace in String 字符串中的查找与替换-排序模拟

Find And Replace in String 字符串中的查找与替换

问题描述：

你会得到一个字符串 s (索引从 0 开始)，你必须对它执行 k 个替换操作。替换操作以三个长度均为 k 的并行数组给出：indices, sources, targets。

要完成第 i 个替换操作:

1. 检查 子字符串 sources[i] 是否出现在 原字符串 s 的索引 indices[i] 处。
2. 如果没有出现， 什么也不做 。
3. 如果出现，则用 targets[i] 替换 该子字符串。

例如，如果 s = "abcd" ， indices[i] = 0 , sources[i] = "ab"， targets[i] = "eee" ，那么替换的结果将是 "eeecd" 。

所有替换操作必须 同时 发生，这意味着替换操作不应该影响彼此的索引。测试用例保证元素间不会重叠 。

• 例如，一个 s = "abc" ， indices = [0,1] ， sources = ["ab"，"bc"] 的测试用例将不会生成，因为 "ab" 和 "bc" 替换重叠。

在对 s 执行所有替换操作后返回 结果字符串 。

子字符串 是字符串中连续的字符序列。

$$\begin{gathered} 1<=s.length<=1000 \\ k==indices.length==sources.length==targets.length \\ 1<=k<=100 \\ 0<=indices[i]<s.length \\ 1<=sources[i].length,targets[i].length<=50 \\ s仅由小写英文字母组成 \\ sources[i]和targets[i]仅由小写英文字母组成 \end{gathered}$$

分析

模拟类型的问题

直接的想法就是依次遍历，遇到一个索引，进行比较，如果于$source[i]$相同，就要替换成为$t[i]$.

当遇到索引$idx=ind[i]$，$ls=source[i].length$.即$s[idx:idx+ls-1]==source[i]$是否相等。

• 如果相等，$s[idx:idx+ls-1]$就需要被替换。因为有限制，所以不会出现重叠的现象。此时$s[idx+ls]$就是未被替换的字符位置，它和下一个待比较的索引位置的关系一定是 $idx+ls<=nextidx$.

所以在2个待比较的索引之间未被替换的字符串的长度是>=0,这一部分就需要加入到结果中。

• 如果不相等，那么$s[idx:nextidx-1]$的字符串就会全部加入结果中。

模拟

这个思路是以待比较的索引从小到大的排列，并且以索引数组为遍历目标，进行模拟。

因此需要对原始的三个数组，进行预处理，即进行索引排序。

代码

排序模拟

class Solution {
    public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
        StringBuilder sb = new StringBuilder();
        char[] arr = s.toCharArray();
        int n = indices.length;
        int len = arr.length;
        Integer[] indarr = new Integer[n];
        for(int i=0;i<n;i++) indarr[i] =i;
        Arrays.sort(indarr,(a,b)->{return indices[a]-indices[b];});
        int end = 0;
        for(int i=0;i<n;i++){
            int idx = indices[indarr[i]];
            String s1 = sources[indarr[i]];
            String t1 = targets[indarr[i]];
            int l1 = s1.length(); 
            if(check(idx,arr,s1)){
                if(end<idx){ 
                    sb.append(s.substring(end,idx));
                } 
                sb.append(t1);
                end = idx+l1;
            }
            else{
                int nx = i+1<n?indices[indarr[i+1]]:len;
                if(idx==nx) continue; 
                sb.append(s.substring(end,idx));
                sb.append(s.substring(idx,nx));
                end = nx;
            } 
        } 
        if(end<len)sb.append(s.substring(end,len));
        return sb.toString();
    }
    public boolean check(int idx,char[] arr,String s){
        int ls = s.length(),n = arr.length;
        int l1 = n-idx; 
        if(l1<ls) return false;
        int ind =0;
        for(int i = idx;i<idx+ls;i++,ind++){             
            if(arr[i]!=s.charAt(ind)) return false;  
        }
        return true;  
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

时间复杂度$O(N+MlogM)$

空间复杂度$O(N+ML)$

还有一种线性的思路，S的长度是N，那么就有可能会在N个位置上进行替换操作。有空再写

Tag

Array

Sort

String