CODEWITHSUNDEEP
javaalgorithm
Ali Jawad
Ali Jawad

Reputation: 151

Efficient Algorithm for character replacement in a string

I have two strings

  1. 111TTT0000TT11T00
  2. 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);
}

Upvotes: 0

Views: 2242

Answers (2)

Ken Bekov
Ken Bekov

Reputation: 14015

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.

Upvotes: 5

Vlad
Vlad

Reputation: 18633

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"));
  }
}

Upvotes: 1

Related Questions