leetcode 833. 字符串中的查找与替换

旧城等待， 2023-06-12 09:59 92阅读 0赞

对于某些字符串 S，我们将执行一些替换操作，用新的字母组替换原有的字母组（不一定大小相同）。

每个替换操作具有 3 个参数：起始索引 i，源字 x 和目标字 y。规则是如果 x 从原始字符串 S 中的位置 i 开始，那么我们将用 y 替换出现的 x。如果没有，我们什么都不做。

举个例子，如果我们有 S = “abcd” 并且我们有一些替换操作 i = 2，x = “cd”，y = “ffff”，那么因为 “cd” 从原始字符串 S 中的位置 2 开始，我们将用 “ffff” 替换它。

再来看 S = “abcd” 上的另一个例子，如果我们有替换操作 i = 0，x = “ab”，y = “eee”，以及另一个替换操作 i = 2，x = “ec”，y = “ffff”，那么第二个操作将不执行任何操作，因为原始字符串中 S\[2\] = ‘c’，与 x\[0\] = ‘e’ 不匹配。

所有这些操作同时发生。保证在替换时不会有任何重叠： S = “abc”, indexes = \[0, 1\], sources = \[“ab”,“bc”\] 不是有效的测试用例。

示例 1：

输入：S = “abcd”, indexes = \[0,2\], sources = \[“a”,“cd”\], targets = \[“eee”,“ffff”\]  
输出：“eeebffff”  
解释：  
“a” 从 S 中的索引 0 开始，所以它被替换为 “eee”。  
“cd” 从 S 中的索引 2 开始，所以它被替换为 “ffff”。  
示例 2：

输入：S = “abcd”, indexes = \[0,2\], sources = \[“ab”,“ec”\], targets = \[“eee”,“ffff”\]  
输出：“eeecd”  
解释：  
“ab” 从 S 中的索引 0 开始，所以它被替换为 “eee”。  
“ec” 没有从原始的 S 中的索引 2 开始，所以它没有被替换。

提示：

0 <= indexes.length = sources.length = targets.length <= 100  
0 < indexes\[i\] < S.length <= 1000  
给定输入中的所有字符都是小写字母。

思路：  
原地修改字符对象S，因为，给出的索引序号都是从，左往右，同时，不满足就断开， 所以这里逆向思维，从右往左，既能做到序号不影响前面的，又能完美解决再开辟一个String保存结果时的索引位置

public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
        
    
                List<int[]> list = new ArrayList<>();
                for (int i = 0;i < indexes.length;i++)
                    list.add(new int[]{
        indexes[i],i});
    
                Collections.sort(list,new Comparator<int[]>(){
        
            
                    @Override
                    public int compare(int[] o1,int[] o2) {
        
    
                         return o2[0]-o1[0];   
                    }
                });
                //Collections.sort(list, Comparator.comparing(i -> -i[0]));
    
                for (int[] index:list) {
        
                    int i = index[0];
                    int j = index[1];
                    String s = sources[j];
                    String t = targets[j];
                if (S.substring(i,i+s.length()).equals(s))
                S = S.substring(0,i) + t + S.substring(i+s.length());
    
                }
                return S;
        }