# 0833. Find And Replace in String
###### tags: `Leetcode` `Medium` `Google`
Link: https://leetcode.com/problems/find-and-replace-in-string/
## 思路 $O(N)$ $O(N)$
$N$为字串长度
先记录一下所有要被替换的位置的起始index(也就是$indices$的子集)，一开始是用list记录起始index在$indices$中的index，也就是把第六行改成```replaceIdx.add(i)```，然后在后面遍历string的时候同时按顺序遍历list，如果遇到一样的，则说明要替换，但是问题是$indices$里面不是按顺序排列的
因此后来选择用map存要被替换的位置在string里面的index，和在$indices$里面对应的index，接下来遍历字串，如果map里面存在i，则说明该处要被替换
## Code

class Solution {
    public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
        Map<Integer, Integer> replaceIdx = new HashMap<>();
        for(int i = 0;i < indices.length;i++){
            if(s.startsWith(sources[i], indices[i])){
                replaceIdx.put(indices[i],i);
            }
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0;i < s.length();i++){
            if(replaceIdx.containsKey(i)){
                sb.append(targets[replaceIdx.get(i)]);
                i += sources[replaceIdx.get(i)].length()-1;
            }
            else{
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}