CODEWITHSUNDEEP
javastringsubstring
mrQWERTY
mrQWERTY

Reputation: 4149

Elegant solution to replace substrings

I have a challenging problem that I am having trouble with. I have an unmodified string, for instance abcdefg and an array of objects that contains a string and indices.

For instance, object 1 contains d and indices [1, 2];

Then I would replace whatever letter is at substring [1,2] with d, with the resulting string looking like adcdefg.

The problem comes when the replacing text is of different length then the replaced text. I need some way to keep track of the length changes or else the indices of further replacements would be inaccurate.

Here is what I have so far:

 for (CandidateResult cResult : candidateResultList) {
      int[] index = cResult.getIndex();

      finalResult = finalResult.substring(0, index[0]) + cResult.getCandidate()
              + finalResult.substring(index[1], finalResult.length()); //should switch to stringbuilder
 }
 return finalResult;

This does not take care of the corner case mentioned above.

Additionally, this is not homework if anyone was wondering. This is actually for an ocr trainer program that I'm creating.

Upvotes: 2

Views: 113

Answers (3)

bcorso
bcorso

Reputation: 47166

Here's an implementation, I haven't tested it yet but you can try to get an idea. I'll add comments to the code as needed.

/** This class represents a replacement of characters in the original String, s[i0:if], 
  *  with a new string, str. 
 **/
class Replacement{
    int s, e;
    String str;
    public Replacement(int s, int e, String str){ 
        this.s = s;
        this.e = e;
        this.str = str;
    }
}

String stringReplace(String str, List<Replacement> replacements){

    // Sort Replacements by starting index
    Collections.sort(replacements, new Comparator<Replacement>(){
        @Override public int compare(Replacement r1, Replacement r2){
            return Integer.compare(r1.s, r2.s);
        }
    };

    StringBuilder sb = new StringBuilder();
    int repPos = 0;

    for(int i = 0; i < str.length; i++){
        Replacement rep = replacements.get(repPos);
        if(rep.s == i){               // Replacement starts here, at i == s
            sb.append(rep.str);       // Append the replacement
            i = rep.e - 1;            // Advance i -> e - 1
            repPos++;                 // Advance repPos by 1
        } else {
            sb.append(str.charAt(i)); // No replacement, append char
        }
    }

    return sb.toString();
}

[Edit:] After seeing ptyx's answer, I think that way is probably more elegant. If you sort in reverse order, you shouldn't have to worry about the different lengths:

String stringReplace(String str, List<Replacement> replacements){

    // Sort Replacements in reverse order by index 
    Collections.sort(replacements, new Comparator<Replacement>(){
        @Override public int compare(Replacement r1, Replacement r2){
            return -Integer.compare(r1.s, r2.s);  // Note reverse order
        }
    };

    // By replacing in reverse order, shouldn't affect next replacement.
    StringBuilder sb = new StringBuilder(str);
    for(Replacement rep : replacements){
        sb.replace(rep.s, rep.e, rep.str);
    }

    return sb.toString();
}

Upvotes: 2

Ash
Ash

Reputation: 101

This seems to do as you ask, basically you just translate the replacement based on previous inserts

public static void main(String[] args) {
    Replacer[] replacers = {
            new Replacer(new int[]{ 1 , 2 }, "ddd") ,
            new Replacer(new int[]{ 2 , 3 }, "a")
    };
    System.out.println(
            m("abcdefg", replacers));
}

public static String m(String s1, Replacer[] replacers){
    StringBuilder builder = new StringBuilder(s1);
    int translate = 0;
    for (int i = 0 ; i < replacers.length ; i++) {
        translate += replacers[i].replace(builder, translate);
    }
    return builder.toString();
}

public static class Replacer{
    int[] arr;
    String toRep;

    public Replacer(int[] arr, String toRep) {
        this.arr = arr;
        this.toRep = toRep;
    }

    public int replace(StringBuilder b, int translate){
        b.replace(arr[0] + translate, arr[1] + translate, toRep);
        return arr[1];
    }
}

Upvotes: 1

ptyx
ptyx

Reputation: 4164

Assuming no overlapping ranges to replace, process your replacements in reverse position order - done.

It doesn't matter what you replace [5-6] with, it will never modify [0-4] therefore you don't need to bother about any index mapping for, for example: [1,2]

Upvotes: 1

Related Questions