Replacing characters in a Java string using iteration and recursion

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 co

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.

StackExchange Code Review Q#139434, answer score: 2