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)

186 - Reverse Words in a String II

Question

Algorithm

Code

All Problems

All Solutions