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)