Efficient Algorithm for character replacement in a string

Question

I have two strings

111TTT0000TT11T00
001101

Now I want to replace all appearances of T in string 1 with character from string 2. Like first T with 0, second T with 0, third T with 1 and so on.

One way of doing so is using while loop and compare every character but in programming sense that's not a good way of acheiving it. Can anybody solve it with better algorithm using JAVA?

public void DataParse(String point, String code)
{

    //////////tln("Point:"+point);
    //////////tln("code:"+code);
    //  //////////tln(baseString_temp);

    int counter=0;

    while(baseString_temp.contains(point))
    {      
        if(code!=null)
        {
            String input=String.valueOf(code.charAt(counter));
            //zzzzz(input);


            baseString_temp=baseString_temp.replaceFirst(point,input);
            counter=counter+1;
        }
    }

    ////////////System.out(baseString_temp);
}

"but in programming sense that's not a good way of acheiving it". Why? — Tunaki
– Tunaki, Commented Feb 5, 2016 at 11:24
Also, post some code of your attempt first so we can guide you from there. — James
– James, Commented Feb 5, 2016 at 11:25
As it involves traversing through complete string, reading every character, comparing it and then replace. If some one could better algo for it. — Ali Jawad
– Ali Jawad, Commented Feb 5, 2016 at 11:25
There is no reason to avoid of loop. You'll need to read every character anyway. There is no method to check and change data but don't read it. — Ken Bekov
– Ken Bekov, Commented Feb 5, 2016 at 11:29
I wouldn't know how to know a character is a 'T' without reading it. Basically the only way to do it is to traverse through the first string and keep a pointer in the second. Any calls of high level functions that search for some character are way to expensive. They traverse through the string as well. Hence multiple calls would cause multiple scans. — Ronald
– Ronald, Commented Feb 5, 2016 at 11:32

Ken Bekov · Accepted Answer · 2016-02-05 12:31:34Z

Every time, when you use contains and replaceFirst, you force your program enumerate string's character from begining. I believe it will be better to do it in single pass:

public static String replaceToken(String primary, String secondary, char token) {

   char [] charArray =primary.toCharArray();

   int counter = 0;
   for(int i=0; i<charArray.length; i++){
       if(charArray[i]==token){
           charArray[i] = secondary.charAt(counter);
           counter++;
           if(counter>=secondary.length()) break;
       }
   }
   return new String(charArray);
}    


public static void main(String[] args) {       
   String result = replaceToken("111TTT0000TT11T00", "001101", 'T');
}

If you realy would like to use RegExp so much, then here you are:

public static String replaceSequence(String primary, String secondary, String sequence){

    Pattern pattern = Pattern.compile(sequence + "+");
    Matcher matcher = pattern.matcher(primary);

    int counter = 0;
    char [] charArray = primary.toCharArray();

    while(matcher.find() && counter<secondary.length()){
        for(int i = matcher.start(); i<matcher.end(); i++){
            charArray[i] = secondary.charAt(counter++);
            if(counter>=secondary.length()) break;
        }
    }
    return new String(charArray);
}

But, based on description of your task, I prefer first approach.

Vlad · Accepted Answer · 2016-02-05 11:36:26Z

There's a couple of things. Because Strings are immutable,

baseString_temp=baseString_temp.replaceFirst(point,input);

will always create a new String object (Also, it goes through the string from the beginning, looking for point). If you use a StringBuilder, you only allocate memory once, and then you can mutate it. Actually, using an array like in Ken's answer would be even better, as it allocates less and has less overhead from method calls.

Also, I'd imagine contains() uses a loop of its own, and in the worst case goes to the end of the string. You only need to iterate over the string once, and replace as you go along.

Working example:

public class Test {

  private static String replace(char what, String input, String repls) {
    StringBuilder sb = new StringBuilder(input);
    int replIdx = 0;
    for (int i = 0; i < input.length(); i++) {
      if (input.charAt(i) == what) {
        sb.setCharAt(i, repls.charAt(replIdx++));
      }
    }
    return sb.toString();
  }

  public static void main(String[] args) {
    System.out.println(replace('T', "111TTT0000TT11T00", "001101"));
  }
}

I forgot to say in my answer that replaceFirst creates new string every time. This will lead to memory spending. That's important note.

Collectives™ on Stack Overflow

Efficient Algorithm for character replacement in a string

2 Answers 2

Comments

1 Comment

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Related