Wednesday, July 17, 2013

String Reverse with n/2 Complexity

The n/2 complexity meaning time require to produce desired output is half . Consider example where we use string reverse , in that case we require to iterate loop over string for each and every element e.g  for i = 0 to i = string.length(). Here in n/2 the loop is half i.e for i = 0 to i = string.length()/2.

Following example shows how to do this !

package string_reverse;

import java.util.Scanner;

public class StrRev {

    public static void main(String[] args) {
        System.out.print("Enter String:");
        Scanner scanner = new Scanner(System.in);
        String enteredStr = scanner.nextLine();

        String reversedStr = stringReverse(enteredStr);
        System.out.println(reversedStr);
    }

    private static String stringReverse(String enteredStr) {
        char temp;
        char[] strRev = enteredStr.toCharArray();
        int len = enteredStr.length();

        for(int i=0;i < len/2;i++){
            temp = strRev[i];
            strRev[i] = strRev[len-i-1];
            strRev[len-i-1] = temp;
        }
        return new String(strRev);
    }
}

The logic behind is to swap first and last element with one iteration and so on . One time you dealing swapping with two character and finally you will get result in n/2 iteration.

No comments:

Post a Comment