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.
Implementation:
#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).
Isn’t is same problem as moving all zeros to end or front in an array?
Yes, it is same.
Here it is changed a bit to make it faster.
public static String moveSpacesToFront(String in){
int i = 0;
while(i<in.length()){
if(in.charAt(i) == ' '){
in = in.substring(0, i) + in.substring(i+1, in.length());
in = '_' + in;
}
i++;
}
return in;
}
public class Lab1 {
public static void main(String[] args) {
String s=”hello how are you”;
char ch [] =s.toCharArray();
int i=1;
int j=0;
while(i<ch.length){
if(ch[i]==' '){
i++;
}else{
ch[++j]=ch[i++];
}
}
char c[] = new char[j+1];
for(int a=0;a<c.length;a++){
c[a]=ch[a];
}
String str= new String(c);
System.out.println(str);
}
}