833. Find And Replace in String

/**

 * 833. Find And Replace in String To some string S, we will perform some replacement operations that replace groups of letters with new ones (not necessarily the same size).

 *

 * Each replacement operation has 3 parameters: a starting index i, a source word x and a target word y.  The rule is that if x starts at position i in the original string S, then we will replace that occurrence of x with y.  If not, we do nothing.

 *

 * For example, if we have S = “abcd” and we have some replacement operation i = 2, x = “cd”, y = “ffff”, then because “cd” starts at position 2 in the original string S, we will replace it with “ffff”.

 *

 * Using another example on S = “abcd”, if we have both the replacement operation i = 0, x = “ab”, y = “eee”, as well as another replacement operation i = 2, x = “ec”, y = “ffff”, this second operation does nothing because in the original string S[2] = ‘c’, which doesn’t match x[0] = ‘e’.

 *

 * All these operations occur simultaneously.  It’s guaranteed that there won’t be any overlap in replacement: for

 * example, S = “abc”, indexes = [0, 1], sources = [“ab”,”bc”] is not a valid test case.

 *

 * Example 1:

 * Input: S = “abcd”, indexes = [0, 2], sources = [“a”, “cd”], targets = [“eee”, “ffff”] Output: “eeebffff” Explanation:

 * “a” starts at index 0 in S, so it’s replaced by “eee”. “cd” starts at index 2 in S, so it’s replaced by “ffff”.

*/

See the solution on github here: https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/FindAndReplaceInAString.java

Observation: We are asked to replace characters in a string with new characters if a certain match is met. Problem can be solved via creating an array, size of which is the string length and for each index mark whether a match exist or not. Once we have the array populated, we can iterate over the characters, copy character from original string into a string builder if match doesn’t exist and if match exists we copy from the target string. Whether characters match can be figured in java with String.startsWith(STRING_TO_BE_CHECKED, index).

Here is the code:

public String findReplaceString(String str, int[] indexes, String[] sourcesP, String[] targetsP) {
    //for each index in the original string, record whether a match exists
    //if match exists record the index where transformation strings exist
    int len = str.length();
    int[] matches = new int[len];
    Arrays.fill(matches, -1); //-1 indicates no match
    //for each possible match candidate run through the below logic
    for (int i = 0; i < indexes.length; i++) {
        int index = indexes[i];
        String source = sourcesP[i];
        if (str.startsWith(source, index)) {
            matches[index] = i;
        }
    }
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < str.length(); ) {
        if (matches[i] > -1) {
            int matchIndex = matches[i];
            String source = sourcesP[matchIndex];
            String target = targetsP[matchIndex];
            builder.append(target);
            i += source.length();
        } else {
            builder.append(str.charAt(i));
            i++;
        }
    }
    return builder.toString();
}