Welcome to Subscribe On Youtube
Question
Formatted question description: https://leetcode.ca/all/186.html
Given a character array s
, reverse the order of the words.
A word is defined as a sequence of non-space characters. The words in s
will be separated by a single space.
Your code must solve the problem in-place, i.e. without allocating extra space.
Example 1:
Input: s = ["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"]
Example 2:
Input: s = ["a"] Output: ["a"]
Constraints:
1 <= s.length <= 105
s[i]
is an English letter (uppercase or lowercase), digit, or space' '
.- There is at least one word in
s
. s
does not contain leading or trailing spaces.- All the words in
s
are guaranteed to be separated by a single 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
-
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; } } } ############ class Solution { public void reverseWords(char[] s) { int n = s.length; for (int i = 0, j = 0; j < n; ++j) { if (s[j] == ' ') { reverse(s, i, j - 1); i = j + 1; } else if (j == n - 1) { reverse(s, i, j); } } reverse(s, 0, n - 1); } private void reverse(char[] s, int i, int j) { for (; i < j; ++i, --j) { char t = s[i]; s[i] = s[j]; s[j] = t; } } }
-
// 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: def reverseWords(self, s: List[str]) -> None: """ Do not return anything, modify s in-place instead. """ def reverse(s, i, j): while i < j: s[i], s[j] = s[j], s[i] i += 1 j -= 1 i, j, n = 0, 0, len(s) while j < n: if s[j] == ' ': reverse(s, i, j - 1) i = j + 1 elif j == n - 1: reverse(s, i, j) j += 1 reverse(s, 0, n - 1) ############ 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)
-
func reverseWords(s []byte) { n := len(s) for i, j := 0, 0; j < n; j++ { if s[j] == ' ' { reverse(s, i, j-1) i = j + 1 } else if j == n-1 { reverse(s, i, j) } } reverse(s, 0, n-1) } func reverse(s []byte, i, j int) { for i < j { s[i], s[j] = s[j], s[i] i++ j-- } }