Reverse Words in a String I II

Leave a comment

November 27, 2016 by oneOokay

Reverse Words in a String I II

Given an input string, reverse the string word by word. A word is defined as a sequence of non-space characters.

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?


I和II的区别在于:

I中,string可能头尾都含space,而且string中的space可能多过一个。

II中,string头尾不含space,而且string中分隔的space一个

做过Rotate Array之后,这题也就ok了,就是要处理一下corner case

  • 首先rotate整个s
  • 接着for-loop s,遇到space则reverse之前的部分
  • corner case:
    • s只有一个词且不含space
public class Solution {
    public void reverseWords(char[] s) {     
        reverse(s, 0, s.length - 1);
        int start = 0;//start从0开始可以处理不包含空格的情况
        for (int i = 0; i < s.length; i ++){
            if (s[i] == ' '){
                reverse(s, start, i - 1);
                start = i + 1;//更新start
            }//处理corner case
            else if (i == s.length - 1){
                reverse(s, start, i);
            }
        }
    }
    
    private void reverse(char[] s, int start, int end){
        while(start < end){
            char c = s[start];
            s[start] = s[end];
            s[end] = c;
            start ++;
            end --;
        }
    }
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: