2023年8月15日每日一题--833. 字符串中的查找与替换

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

题目分析

方案一

class Solution {  
    public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {  
        StringBuilder result = new StringBuilder(s);  
        int changeIndex = 0;  
        boolean flag = false;  
  
        int[][] indicesIndex = new int[indices.length][2]; // 准备一个中间的变量，用于保存原始的位置信息和数值信息  
        for (int i = 0; i < indices.length; i++) {  
            indicesIndex[i][0] = indices[i];  
            indicesIndex[i][1] = i;  
        }  
        Arrays.sort(indicesIndex, (o1, o2) -> o1[0] - o2[0]); // 对其进行排序  
  
        for (int i = 0; i < indicesIndex.length; i++) {  
  
            while (i < indicesIndex.length - 1 && indicesIndex[i][0] + sources[indicesIndex[i][1]].length() > indicesIndex[i + 1][0]) { // 判断是否右冲突的情况  
                i++;  
                flag = true;  
            }  
            if (false) { // 此时i也是冲突的，需要跳过去  
                i++;  
                flag = false;  
                continue;            }  
  
            //将原始的字符串进行切分，判断其是否等于 sources 中的数据  
            if (result.substring(changeIndex + indicesIndex[i][0], changeIndex + indicesIndex[i][0] + sources[indicesIndex[i][1]].length()).equals(sources[indicesIndex[i][1]])) {  
                result.delete(changeIndex + indicesIndex[i][0], changeIndex + indicesIndex[i][0] + sources[indicesIndex[i][1]].length()); // 删除原有的数据  
                result.insert(changeIndex + indicesIndex[i][0], targets[indicesIndex[i][1]]); // 添加上需要添加的数据  
                changeIndex += targets[indicesIndex[i][1]].length() - sources[indicesIndex[i][1]].length(); // 更新与原字符串相比，其增加或者减少了多少位  
            }  
        }  
          
        return result.toString();  
    }  
}

结果

解答成功:
执行耗时:2 ms,击败了69.90% 的Java用户
内存消耗:40.3 MB,击败了66.99% 的Java用户

分析

时间复杂度：
O( n logn )

空间复杂度：
O( n )

官方题解

https://leetcode.cn/problems/find-and-replace-in-string/solutions/2387388/zi-fu-chuan-zhong-de-cha-zhao-yu-ti-huan-9ns4/

方法一：按照下标排序 + 模拟

class Solution {
    public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
        int n = s.length(), m = indices.length;

        List<Integer> ops = new ArrayList<>();
        for (int i = 0; i < m; i++) {
            ops.add(i);
        }
        ops.sort((i, j) -> indices[i] - indices[j]);

        StringBuilder ans = new StringBuilder();
        int pt = 0;
        for (int i = 0; i < n;) {
            while (pt < m && indices[ops.get(pt)] < i) {
                pt++;
            }
            boolean succeed = false;
            while (pt < m && indices[ops.get(pt)] == i) {
                if (s.substring(i, Math.min(i + sources[ops.get(pt)].length(), n)).equals(sources[ops.get(pt)])) {
                    succeed = true;
                    break;
                }
                pt++;
            }
            if (succeed) {
                ans.append(targets[ops.get(pt)]);
                i += sources[ops.get(pt)].length();
            } else {
                ans.append(s.charAt(i));
                i++;
            }
        }
        return ans.toString();
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/find-and-replace-in-string/solutions/2387388/zi-fu-chuan-zhong-de-cha-zhao-yu-ti-huan-9ns4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

方法二：哈希表 + 模拟

class Solution {
    public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
        int n = s.length(), m = indices.length;

        Map<Integer, List<Integer>> ops = new HashMap<Integer, List<Integer>>();
        for (int i = 0; i < m; ++i) {
            ops.putIfAbsent(indices[i], new ArrayList<Integer>());
            ops.get(indices[i]).add(i);
        }

        StringBuilder ans = new StringBuilder();
        for (int i = 0; i < n;) {
            boolean succeed = false;
            if (ops.containsKey(i)) {
                for (int pt : ops.get(i)) {
                    if (s.substring(i, Math.min(i + sources[pt].length(), n)).equals(sources[pt])) {
                        succeed = true;
                        ans.append(targets[pt]);
                        i += sources[pt].length();
                        break;
                    }
                }
            }
            if (!succeed) {
                ans.append(s.charAt(i));
                ++i;
            }
        }
        return ans.toString();
    }
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/find-and-replace-in-string/solutions/2387388/zi-fu-chuan-zhong-de-cha-zhao-yu-ti-huan-9ns4/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。