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--
    	}
    }
    

All Problems

All Solutions