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.