5
\$\begingroup\$

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

                }






        }



}
\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ I'm not a fan of littering the parameters with final declarations. \$\endgroup\$ – 200_success Aug 23 '16 at 15:51
  • \$\begingroup\$ @200_success It is pretty much opinion-based. I prefer to make it explicit that the value/reference is not modified. \$\endgroup\$ – coderodde Aug 23 '16 at 15:52
  • 6
    \$\begingroup\$ final for arguments is a two-fold knife. As Java is pass-by-value usually assigning new values to these arguments inside the method has no effect to the passed value in the outside world. The only thing they really prevent is, that you unintentionally assign a new value to the argument inside the method itself. However, what final still does not prevent is adding or removing values from/to objects, like Lists and what not making it possible to fill or empty a list inside a method. So if you are not fully aware of its semantics it might be rather misleading, especially for beginners :) \$\endgroup\$ – Roman Vottner Aug 23 '16 at 17:38
  • \$\begingroup\$ OK, you got me convinced; removed the keyword from the answer. \$\endgroup\$ – coderodde Aug 23 '16 at 17:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.