Leetcode 833: String replacement depend upon index numbering

Question

String index value accessThis question is a part of my previous question .

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.

Example 2: Input: S = "abcd", indexes = [0,2], sources = ["ab","ec"], targets = ["eee","ffff"] Output: "eeecd" Explanation: "ab" starts at index 0 in S, so it's replaced by "eee". "ec" doesn't starts at index 2 in the original S, so we do nothing.

public class Q833 {
public static void main(String args[]){
    String S="abcd";
    int[] indexes  = {0, 2};
    String[]sources={"ab","cd"};
    String[] targets = {"eee", "ffff"};
    Solve833 ob833=new Solve833();
    System.out.println(ob833.findReplaceString(S,indexes,sources,targets));
}
}
 class Solve833{
 public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
    char[] array = S.toCharArray();
    StringBuilder result = new StringBuilder();
    int counter = 0;
    String s = "";
    for (String n:sources)
        s+= n;
    char[] c = s.toCharArray();

    for (int i = 0; i < array.length; i++) {
        if(array[indexes[counter]]==c[counter]){
            result.append(targets[counter]);
            if(counter<=indexes.length) {
                counter++;
            }

        }
        else
            result.append(array[i]);
    }


    return result.toString();
}

}

Code Output: for 1st example

Expected output:Output: "eeebffff".

My output:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 2 at Leetcode.Solve833.findReplaceString(Q833.java:30) at Leetcode.Q833.main(Q833.java:16)

Code Output:2nd example

Expected Output: "eeecd"

My Output: eeebcd. So here a b missing. How can I handle it?

Answer 1

Your problem is that you should NOT do array[indexes[counter]]==c[counter] to determine that if the i-thsource string is presented in the S at index i. Your juegement only check for the first character of the source string.

The key of this problem is how can we find the index correctly, as when we are trying to get the result, the index(where to replce the source string with target string) may change.

try this code:

  public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
        StringBuilder sb=new StringBuilder(S);
        int[] offsets=new int[indexes.length];

        for(int i=0;i<indexes.length;i++){

            if(S.substring(indexes[i],indexes[i]+sources[i].length()).equals(sources[i])){
                int offset=0;
                for(int j=0;j<i;j++){
                    if(indexes[j]<indexes[i])
                    offset+=offsets[j];
                }
                sb.replace(indexes[i]+offset,indexes[i]+sources[i].length()+offset,targets[i]);
                offsets[i]=targets[i].length()-sources[i].length();

            }
        }

        return sb.toString();
    }