Question

Formatted question description: https://leetcode.ca/all/186.html

 186	Reverse Words in a String II

 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?

Algorithm

First flip each word, then the entire string,

Or you can reverse the order, first flip the entire string, and then flip each word.

Code

Java

  • 
    public class Reverse_Words_in_a_String_II {
    
        public void reverseWords(char[] s) {
            reverse(s, 0, s.length);
    
            int l = 0; // left
            int r = 0; // right
            while (r <= s.length) {
                if (r == s.length || s[r] == ' ') {
                    reverse(s, l, r);
                    l = r + 1; // +1 to skip space
                }
    
                r++;
            }
        }
    
        // end is exclusive
        private void reverse(char[] s, int begin, int end) {
            for (int i = 0; i < (end - begin) / 2; i++) {
                char temp = s[begin + i];
                s[begin + i] = s[end - i - 1];
                s[end - i - 1] = temp;
            }
        }
    
    }
    
  • // OJ: https://leetcode.com/problems/reverse-words-in-a-string-ii/
    // Time: O(N)
    // Space: O(1)
    class Solution {
    public:
        void reverseWords(vector<char>& s) {
            int i = 0, N = s.size();
            while (i < N) {
                int start = i;
                while (i < N && s[i] != ' ') ++i;
                reverse(begin(s) + start, begin(s) + i);
                ++i;
            }
            reverse(begin(s), end(s));
        }
    };
    
  • class Solution:
      # @param s, a list of 1 length strings, e.g., s = ['h','e','l','l','o']
      # @return nothing
      def reverseWords(self, s):
        def swap(start, end, slist):
          while start < end:
            slist[start], slist[end] = slist[end], slist[start]
            start += 1
            end -= 1
    
        wstart, wend = 0, 0
        for i in range(0, len(s)):
          if s[i] == " ":
            wend = i - 1
            swap(wstart, wend, s)
            wstart = i + 1
          elif i + 1 == len(s):
            swap(wstart, i, s)
    
        swap(0, len(s) - 1, s)
    
    

All Problems

All Solutions