Problem: Given a string that has set of words and
spaces, write a program to move the spaces to front of string, you need
to traverse the array only once and need to adjust the string in place.
string = “move these spaces to beginning”
output =” movethesepacestobeginning”
Solution:
1) Maintain two indices i and j.
2) Traverse from end to beginning.
If the current index contains char, swap chars in index i with index j.
This will move all the spaces to beginning of the array.
Time Complexity: O(n) where n is the number of characters in input array.
Space Complexity: O(1).
string = “move these spaces to beginning”
output =” movethesepacestobeginning”
Solution:
1) Maintain two indices i and j.
2) Traverse from end to beginning.
If the current index contains char, swap chars in index i with index j.
This will move all the spaces to beginning of the array.
#include<iostream> using namespace std; int main() { char a[]="Move space to begining"; int n=strlen(a)-1,count = n; //MoveSpace(a,0,strlen(a)-1); for(int i=n;i>=0;i--) { if(a[i] != ' ') a[count--] = a[i]; } while(count>=0) a[count--] = ' '; cout << "After Space Moved to Begining" << a << endl; return 0; }
Time Complexity: O(n) where n is the number of characters in input array.
Space Complexity: O(1).
0 comments:
Post a Comment