12/21/2012

Implementation of string replace method in JAVA


The idea is to create a custom implementation of the well known method in java, which replaces substring of a string with other string.
Example:

String str1 = "Lyubomir";
System.out.println(str1.replace("Ly", "fiko"));

Result: fikoubomir

The method will be implemented using arrays or characters, although Strings can be used as well. This will be much simple, but the idea here is to get more details in how the algorithm works.

On the first pass we have to calculate how many times the string which will be replaced occurs in the input string.

private static int countNumFimesOneStrInOther(char[] str1Arr,char[] str2Arr )
{
      //count how many times the second string is in the first one
      int counter=0;
      for(int i=0; ilength
; i++){
 int j=i;
     int k=0;
     while(jlength
&& klength && str1Arr[j]==str2Arr[k])
     {         
          j++;
          k++;
     }

       //the whole string 2 is in string one
    if(k==str2Arr.length)
    {
       counter++;
    }
       }
    return counter;
}

Here for every character in the truing we check the characters in the second string, if they are the same as the ones in the first characters increment the counter. Then if the counter is equal to the size of the array - then this is occurrence.

This will give the size of the resulting character array - the size of the string - number of times the second string occurs*it's length  + number of times the second string occurs * it's length: 


char[] strResult = new char[str1Arr.length + Math.abs(numTimes*(str3Arr.length-str2Arr.length))];


Again when the whole string 2 is found in string one - iterate through the third string and put it's character by character in the result string.

Here is the full source code of the program:

import java.util.Hashtable;
import java.io.Console;
import java.util.*;
import java.io.*;
import java.lang.*;

//replace all the strings with string
public class StringReplace {
    public static void main(String[] args)
    {  
        String str1 = args[0];
        String str2 = args[1];
        String str3 = args[2];

        System.out.println(replace(str1, str2, str3));
   }

   private static int countNumFimesOneStrInOther(char[] str1Arr,char[] str2Arr )
   {
        //count how many times the second string is in the first one
        int counter=0;
        for(int i=0; ilength
; i++)         {
            int j=i;
            int k=0;
            while(jlength
&& klength && str1Arr[j]==str2Arr[k])             {
                j++;
                k++;
            }

            //the whole string 2 is in string one
            if(k==str2Arr.length)
            {
                counter++;
            }
        }
        return counter;
   }

    private static String replace(String str1, String str2, String str3)
    {
        if(str1==null || str2==null)
            return "";
      

        char[] str1Arr = str1.toCharArray();
        char[] str2Arr = str2.toCharArray();
        char[] str3Arr = str3.toCharArray();

        int numTimes = countNumFimesOneStrInOther(str1Arr, str2Arr);

        //the result string will be with length x times the number of times the string which replaces the first one occurs
        char[] strResult = new char[str1Arr.length + Math.abs(numTimes*(str3Arr.length-str2Arr.length))];

        int resIndex=0;
        for(int i=0; ilength
; i++)         {
            int j=i;
            int k=0;
            
            while(jlength
&& klength && str1Arr[j]==str2Arr[k])             {
                j++;
                k++;
            }

            //the whole string 2 is in string one
            if(k==str2Arr.length)
            {
                k=0;
                while(klength
)                 {
                    strResult[resIndex] = str3Arr[k];
                    resIndex++;
                    k++;
                    i++;
                }
            }
            
            strResult[resIndex] = str1Arr[i];
            resIndex++;
            
        }
            
        return new String(strResult);
    }
}



The complexity of the method is O(n^2) and the space needed is O(m - k.n + k.p), where n-the size of the replaced string, p-the size of the string replacement.

Better solution will be to use suffix tree or suffix array data structure - which gives the index on the substring in linear time and uses no extra space.








0 comments: