Reverse Words in a String
leetcode: https://leetcode.com/problems/reverse-words-in-a-string/
Description:
Given an input string s, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.
Return a string of the words in reverse order concatenated by a single space.
Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.
Idea:
Solution1:
Step1: remove extra space of the string
Step2: reverse the whole string, and then reverse each word in the string
Step3: use two pointer to implement the reverse specified range
Step4: in the remove extra space method, first use loop to get the index after all space at the begainning. then use loop to traverse from the end, to get the index before all space at the end of the string.
To remove duplicate space inside the string, traverse the element and use new string to store the character isn’t space, or if the character is space, but the last element in the new string isn’t space, then store the space.(it ensures in the new string, there are no continuously space.)
Step 5: set two pointer to get the range of each word in the string, at the beginning, two pointes point to 0 and 1 seperately. then traverse the string(until the first point exceed the string), if the next element is space, then use scend pointer to get the index. then reverse the word in the range(first index, second index -1). make first index equal to second index+1, and second index point to next element.
Code:
class Solution {
public String reverseWords(String s) {
if (s.length() == 0){
return s;
}
char[] result = trim(s).toCharArray();
int length = result.length;
reverse(result,0,length-1);
// reverse each word
int start = 0;
int end = 1;
while(start < length){
while(end < length && result[end]!=' '){
end++;
}
reverse(result,start,end-1);
start = end +1;
end = start + 1;
}
return new String(result);
}
public String trim(String s){
int start = 0;
int end = s.length()-1;
String string1 ="";
// remove all space in the begainning of the string
while(start<=end && s.charAt(start) ==' '){
start++;
}
//remove all space at the end of the string
while (start<=end && s.charAt(end) ==' '){
end--;
}
//remove the extra space in the string
while(start<=end){
if (s.charAt(start) != ' '){
string1 += s.charAt(start);
}
// when the character is space, but the end character of the result string is not space, then store it
else if(s.charAt(start) == ' ' && string1.charAt(string1.length()-1) != ' '){
string1 += s.charAt(start);
}
start++;
}
return string1;
}
public void reverse(char[]s, int i, int j){
while(i<j){
char temp = s[i];
s[i] = s[j];
s[j] = temp;
i++;
j--;
}
}
}
Solution2:
Use new char array to store the character one by one
Step1: create new char array and make the size of it as the original array’s length +1
Step2: traverse the string from the end of the string, and use firtst pointer to get the index that before all space after the word.
Step3: then use the second pointer to record this index, continue traverse until the character is space. then traverse characters between two pointers one by one through putting them to the new array. and add one space in the world.
Step4: delete the last element of the array, because we will add one more space in the last word.
Code:
class Solution {
public String reverseWords(String s) {
char[] sa = s.toCharArray();
char[] result = new char[sa.length+1];
// set the index for result array
int index = 0;
// set first pointer
int i = sa.length -1;
while(i>=0){
// avoid space
while(i>=0 && sa[i] == ' '){
i--;
}
// set second pointer
int second = i;
while(i>=0 && sa[i] !=' '){
i--;
}
for (int j = i+1; j<=second; j++){
result[index++] = sa[j];
if (j==second){
result[index++] = ' ';
}
}
}
// because we add one more space in the end of the array
return new String(result,0,index-1);
}
}