[LeetCode] 833 Find And Replace in String (Week 7, No.3)

Description

You are given a 0-indexed string s that you must perform k replacement operations on. The replacement operations are given as three 0-indexed parallel arrays, indices, sources, and targets, all of length k.

To complete the i^th replacement operation:

1. Check if the substring sources[i] occurs at index indices[i] in the original string s.
2. If it does not occur, do nothing.
3. Otherwise if it does occur, replace that substring with targets[i].

For example, if s = "abcd", indices[i] = 0, sources[i] = "ab", and targets[i] = "eee", then the result of this replacement will be "eeecd".

All replacement operations must occur simultaneously, meaning the replacement operations should not affect the indexing of each other. The testcases will be generated such that the replacements will not overlap.

• For example, a testcase with s = "abc", indices = [0, 1], and ources = ["ab","bc"] will not be generated because the "ab" and "bc" replacements overlap.

Return the resulting string after performing all replacement operations on s.

A substring is a contiguous sequence of characters in a string.

Example 1:

Input: s = "abcd", indices = [0, 2], sources = ["a", "cd"], targets = ["eee", "ffff"]
Output: "eeebffff"
Explanation:
"a" occurs at index 0 in s, so we replace it with "eee".
"cd" occurs at index 2 in s, so we replace it with "ffff".

Example 2:

Input: s = "abcd", indices = [0, 2], sources = ["ab","ec"], targets = ["eee","ffff"]
Output: "eeecd"
Explanation:
"ab" occurs at index 0 in s, so we replace it with "eee".
"ec" does not occur at index 2 in s, so we do nothing.

Constraints:

• 1 <= s.length <= 1000
• k == indices.length == sources.length == targets.length
• 1 <= k <= 100
• 0 <= indexes[i] < s.length
• 1 <= sources[i].length, targets[i].length <= 50
• s consists of only lowercase English letters.
• sources[i] and targets[i] consist of only lowercase English letters.

---

풀이

각 indices와 source, target을 짝지어 해시맵에 넣어둔 뒤 indices를 정렬했다.
hashmap <indices[i], [sources[i], targets[i]]>

s의 처음부터 끝 문자까지 돌면서 indices를 본다.
맨 처음 indices가 0이 아니면 현재 indices 전까지 s의 문자를 sb에 붙인다.
현재 인덱스부터 sources[i]의 길이 만큼 잘라서 substring으로 만들고, 이 substring이 sources[i]와 같은지 비교한다.
같다면 targets[i]를 sb에 붙인다.
다르다면 원래의 substring를 그대로 넣는다.
substring으로 자르고 다음 indices까지 남는 문자가 있다면 그대로 sb에 붙여준다.
맨 마지막은 indices에 비교할 문자가 있는지 보고, 있다면 위와 같은 방법으로 비교하여 targets[i]를 넣는다.
없다면 남은 문자열을 모두 sb에 붙여준다.

연산이 다 끝나면 sb를 문자열로 바꾸어 반환한다.

---

코드

indices의 인덱스 단위로 비교

class Solution {
    public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
        //base case
        if (s.length() == 1) {
            if (indices[0] != 0)
                return s;
            else if (s.equals(sources[0]))
                return targets[0];
            else
                return s;
        }

        StringBuilder sb = new StringBuilder();

        int curIdx = indices[0];
        int nextIdx, nextSubIdx;

        if (indices.length == 1) {
            // 맨 처음 idx가 0이 아니면 원본을 붙여줘야 한다.
            if (curIdx != 0) {
                sb.append(s, 0, curIdx);
            }

            nextIdx = curIdx + sources[0].length();
            String subString = s.substring(curIdx, nextIdx);
            if (subString.equals(sources[0])) { // 같을 때
                sb.append(targets[0]);
                if (nextIdx != s.length()) {    // 남은 문자가 있을 때
                    sb.append(s.substring(nextIdx));
                }
            } else {    // 같지 않을 때
                sb.append(s, curIdx, s.length());
            }
            return sb.toString();
        }

        HashMap<Integer, String[]> map = new HashMap<>();
        for (int i = 0; i < indices.length; i++) {
            map.put(indices[i], new String[]{sources[i], targets[i]});
        }
        Arrays.sort(indices);

        for (int i = 0; i < indices.length - 1; i++) {
            curIdx = indices[i];
            nextIdx = indices[i + 1];
            String[] curMapVal = map.get(curIdx);
            String curSource = curMapVal[0];
            String curTarget = curMapVal[1];
            nextSubIdx = curIdx + curSource.length();

            // 맨 처음 idx가 0이 아닌 경우 - 처음부터 현재 인덱스 전까지의 문자를 그대로 붙인다.
            if (i == 0 && curIdx != 0) {
                sb.append(s, 0, curIdx);
            }
            
            String subString = s.substring(curIdx, nextSubIdx);
            if (subString.equals(curSource)) {  // 같을 때
                sb.append(curTarget);
                if (nextSubIdx != nextIdx) {    // 남은 문자가 있을 때
                    sb.append(s, nextSubIdx, nextIdx);
                }
            } else {    // 다를 때
                sb.append(s, curIdx, nextIdx);
            }
        }

        // 마지막 indices[]
        curIdx = indices[indices.length - 1];

        String[] curMapVal = map.get(curIdx);
        String curSource = curMapVal[0];
        String curTarget = curMapVal[1];

        nextSubIdx = curIdx + curSource.length();

        String subString = s.substring(curIdx, nextSubIdx);
        if (subString.equals(curSource)) { // 문자가 같을 때
            sb.append(curTarget);
            if (nextSubIdx != s.length()) { // 남은 문자가 있을 때
                sb.append(s.substring(nextSubIdx));
            }
        } else {    // 문자가 다를 때
            sb.append(s.substring(curIdx));
        }
        
        return sb.toString();
    }
}

한 문자씩 비교

class Solution {
    public String findReplaceString(String s, int[] indices, String[] sources, String[] targets) {
        StringBuilder sb = new StringBuilder();
        HashMap<Integer, String[]> compareMap = new HashMap<>();
        int[] existList = new int[s.length()]; 

        for (int i = 0; i < indices.length; i++) {
            compareMap.put(indices[i], new String[]{sources[i], targets[i]});
            existList[indices[i]] = sources[i].length(); // 비교할 문자의 개수 저장
        }

        int start = 0;
        while (start < s.length()) {
            if (existList[start] == 0) {    // 매칭할 단어가 없을 때
                sb.append(s.charAt(start));
                start++;
            } else {	// 매칭할 단어가 있을 때
                String[] curCompare = compareMap.get(start);
                String curSource = curCompare[0];
                String curTarget = curCompare[1];
                String subString = s.substring(start, start + existList[start]);
                if (subString.equals(curSource)) {
                    sb.append(curTarget);
                } else {
                    sb.append(s, start, start + existList[start]);
                }
                start += existList[start];
            }
        }

        return sb.toString();
    }
}
``