Sunday, March 1, 2015

186. Reverse Words in a String II ---M

Given an input string , reverse the string word by word. 

Example:

Input:  ["t","h","e"," ","s","k","y"," ","i","s"," ","b","l","u","e"]
Output: ["b","l","u","e"," ","i","s"," ","s","k","y"," ","t","h","e"]

Note: 

  • A word is defined as a sequence of non-space characters.
  • The input string does not contain leading or trailing spaces.
  • The words are always separated by a single space.

Follow up: Could you do it in-place without allocating extra space?

A:
就是先完全reverse, 再在单词内部 逆转回来

class Solution {
public:
    void reverseWords(vector<char>& s) {
        helper(s,0,s.size()-1);
        int start = 0;
        for(int i = 0;i<=s.size();i++){
            if(i==s.size() || s[i]==' '){ // need check edge before check value
                helper(s,start,i-1);
                start = i+1;
            }
        }
    }
private:
    void helper(vector<char> & s, int start, int end){
        while(start <end){
            char tmp = s[start];
            s[start] = s[end];
            s[end] = tmp;
            start++;
            end--;
        }
    }
};


Mistakes:
1 : if(i==s.size() || s[i]==' '){ // need check edge before check value。 
一开始写成了 if(s[i]==' ' || i==s.size() )          造成越界







No comments:

Post a Comment