The input string does not contain leading or trailing spaces and the words are always separated by a single space.
For example,
Given s = "the sky is blue",
return "blue is sky the".
Could you do it in-place without allocating extra space?
Idea: Reverse twice, both in place.
Time: O(n) Space: O(1)
Code:
public class Solution {
public void reverseWords(char[] s) {
if(s==null||s.length==0)
return;
reverse(s,0,s.length-1);
for(int left=0;left<s.length;left++)
{
if(s[left]!=' ')
{
int right=left;
while(right<s.length&&s[right]!=' ')
right++;
reverse(s,left,right-1);
left=right;
}
}
}
public void reverse(char[] chars, int start,int end)
{
for(int i=start,j=end;i<j;i++,j--)
{
char tmp=chars[i];
chars[i]=chars[j];
chars[j]=tmp;
}
}
}
No comments:
Post a Comment