Replacing characters in a Java string using iteration and recursion

Question

I am new to the whole Data Structures thing and I want to get better at writing efficient code. So, I have been practicing some problem sets. The questions is - Replace characters in a string using iteration and recursion approach. I am still learning the whole recursion approach. But I tried to design an algorithm using the divide and conquer approach. I would like to know if there is any where I can fix my code and make it better.

I wrote the code using both approaches. Iteration and Recursion. I will be really thankful if I can get valuable pointers to improve my code and make it more efficient.

public class MainClass {

    public static void main(String[] args) {
        // TODO Auto-generated method stub

         String text = "Hello World !"
                + "Hello";

         if(!text.isEmpty())
         {
         //Method 1 Iteration approach
         System.out.println("Replacing Characters using Iteration Approach");
         System.out.println(replace(text,'o','s'));

         //Method 2 Recursion approach
         char [] temp = new char[text.length()];
         temp = text.toCharArray();

        recursiveapproach(temp,0,temp.length,'o','s');
        System.out.println("Replacing characters using Recursion Approach");
        System.out.print(String.valueOf(temp));
         }




        else
        {
            System.out.println("Empty String");
        }





    }

    public static String replace(String str, char ch,char r)
    {
        char[] c = new char [str.length()]; // O(1);



            c = str.toCharArray(); //assuming it to be O(1)
            for(int i=0;i<c.length;i++)//O(n)
            {
                if(ch==c[i]) // O(1)
                {
                    c[i] = r; // O(1)
                }
            }

            //for(int i=0;i<c.length;i++)
                //System.out.print(c[i] + "\t");



        String s = String.valueOf(c); //// O(1)

        return s; //// O(1)


        // Time complexity is O(n) for the above code.




    }

     public static void replacechar(char[] a,int start,char c,char r)
        {

            if(a[start]== c)
            {
                a[start] = r;

            }
        }
        public static void recursiveapproach(char[] a,int start,int end,char c,char r)
        {




            int mid;

          int s = a.length-1;

            if(start<end)
            {
                mid = start + (end - start)/2;


                recursiveapproach(a,start,mid,c,r);


                recursiveapproach(a,mid+1,end,c,r);



            }


                if(start==end && start<=s)
                {

                replacechar(a,start,c,r);

                }






        }



}

Answer 1

First of all, good work!

Now a couple of points:

Whitespace

You abuse the usage of white space in your code. This applies to indentation as well.

\$\mathcal{O}(?)\$

You are right about the running time of both your methods being \$\mathcal{O}(n)\$ (in all cases). However,

str.toCharArray(); //assuming it to be O(1)

runs in linear time as well (apart from counting the time it takes to ask the memory subsystem for a new character array). The issue here is that, the returned array is not the same array somewhere in the str, and that's why: if it were the same array, it would run in constant time, yes, but it would allow a programmer to modify the state of the string through the character array.

API design

You can improve the API of your methods a bit; see below.

Naming

The names c and r are not descriptive. Consider renaming to targetChar(acter) and replacementChar(acter), respectively.

replacechar(...)

Consider renaming to replaceChar(acter), and declare it private since it is an auxiliary method.

Summa summarum

All in all, I had this in mind:

public static String replace(String str, 
                             char targetChar, 
                             char replaceChar) {
    // O(n): Strings are immutable. For that very reason, toCharArray() 
    // returns the copy of the internal character array, so that the user
    // cannot mutate the string. Copying done in linear time.
    char[] c = str.toCharArray();

    for (int i = 0; i < c.length; ++i) {
        if (c[i] == targetChar) {
            c[i]= replaceChar;
        }
    }

    return String.valueOf(c);
}

public static void recursiveApproach(String text, 
                                     char targetChar,
                                     char replacementChar) {
    recursiveApproach(text.toCharArray(), targetChar, replacementChar);
}

public static void recursiveApproach(char[] a, 
                                     char targetChar, 
                                     char replacementChar) {
    recursiveApproach(a, 0, a.length, targetChar, replacementChar);
}

public static void recursiveApproach(String text,
                                     int fromIndex,
                                     int toIndex,
                                     char targetChar,
                                     char replacementChar) {
    recursiveApproach(text.toCharArray(),
                      fromIndex,
                      toIndex,
                      targetChar,
                      replacementChar);
}

public static void recursiveApproach(char[] a, 
                                     int fromIndex, 
                                     int toIndex, 
                                     char targetChar, 
                                     char replacementChar) {
    int rangeLength = toIndex - fromIndex;

    if (rangeLength < 1) {
        return;
    } 

    if (rangeLength == 1) {
        replaceChar(a, fromIndex, targetChar, replacementChar);
    } else {
        int mid = fromIndex + rangeLength / 2;
        recursiveApproach(a, fromIndex, mid, targetChar, replacementChar);
        recursiveApproach(a, mid, toIndex, targetChar, replacementChar);
    } 
}

private static void replaceChar(char[] a,
                                int index, 
                                char targetChar, 
                                char replacementChar) {
    if (a[index] == targetChar) {
        a[index] = replacementChar;
    }
}

Hope that helps.