Problem Statement:
Reverse Words of the String given in the form of Character array without additional space.
Download Source Code
Solution:
1st Approach:
Our first approach will require K-1 iterations inorder to get the desired result , where K is the number of words, in each iteration we will move the first word to the end.
At every iteration we will have to hold 1 word in temp memory. Since this approach requires memory equal to 1 word, we will move to our in-place approach.
Time Complexity : O(KN) , where K is number of words and N is the Size of character array.
2nd Approach :
We can divide this approach in two steps.
1. Reverse the character array completely.
2. Reverse each word in the reverse array.
Lets show this by the diagram.
Lets implement the above logic.
Output is :
Time Complexity: O(n)
Space Complexity: O(1)
Please post your comments , queries or any suggestions.
Happy Coding !! :)
Reverse Words of the String given in the form of Character array without additional space.
 |
| Fig 1 |
Solution:
1st Approach:
Our first approach will require K-1 iterations inorder to get the desired result , where K is the number of words, in each iteration we will move the first word to the end.
 |
| Fig 2 |
At every iteration we will have to hold 1 word in temp memory. Since this approach requires memory equal to 1 word, we will move to our in-place approach.
Time Complexity : O(KN) , where K is number of words and N is the Size of character array.
2nd Approach :
We can divide this approach in two steps.
1. Reverse the character array completely.
2. Reverse each word in the reverse array.
Lets show this by the diagram.
 |
| Fig 3 |
Lets implement the above logic.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 | /**Reverse Words in an array */ private static void reverseWords(char[] str) { if(str==null || str.length==0) return ; String temp = new String(str); int len = str.length, l=0,r=0; //Reverse the input array reverseArr(str, 0, str.length-1); while(r<len && str[r] == ' ') //Skip initial Spaces, if any r++; while(r<len) { l=r; //l hold the start character of the word while(r== len-2 || (r<len-1 && str[r+1] != ' ')) //Get the last character of the word in r r++; reverseArr(str,l,r++); while(r<len && str[r] == ' ') //Find the next character using r r++; } System.out.println(temp +" ----> " +new String(str)); } /** * Reverse the character array between i and j (inclusive) */ private static void reverseArr(char[] s,int i, int j) { int len=i+(j-i)/2; //look carefully this line, when i is not 0 for(;i<=len;i++,j--) swap(s,i,j); } /** * Swaps the ith and jth indices */ private static void swap(char[] arr,int i, int j) { char temp = arr[i]; arr[i] = arr[j]; arr[j]=temp; } public static void main(String[] args) { String s1 = " Coding Recipes is Super Cool "; String s2 = "I live to code"; String s3 = "Recursion is Recursion"; //reverseWords1(s.toCharArray()); reverseWords(s1.toCharArray()); reverseWords(s2.toCharArray()); reverseWords(s3.toCharArray()); reverseWords(" ".toCharArray()); reverseWords(null); } |
Output is :
Coding Recipes is Super Cool ----> Cool Super is Recipes Coding
I live to code ----> code to live I
Recursion is Recursion ----> Recursion is Recursion
Time Complexity: O(n)
Space Complexity: O(1)
Please post your comments , queries or any suggestions.
Happy Coding !! :)
No comments:
Post a Comment