151. Reverse Words in a String

Description of the Problem

Given an input string 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 at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

Input: s = "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: s = "  hello world  "
Output: "world hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: s = "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Constraints:

1 <= s.length <= 104
s contains English letters (upper-case and lower-case), digits, and spaces ' '.
There is at least one word in s.

Follow-up: If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

Solution

Tags: Memory Management

Explanation

Simple Idea:

To reverse each word in a string, do mirroring to each word and then do mirroring to the whole string.
To do mirroring for each word, we have to scan each word (using sliding windows, i.e. tokenise)
The follow-up question requires us to do almost any operations in-place. We can first copy each token to suitable place by sliding windows method. For example, ____ABC becomes ABC_ABC.

Reminder:

(*) To fullfill the follow-up question, do not create too much copy of the String. Keep in mind that even if some methods/functions do not have new keyword, the code behind these methods/functions may contain new keyword in their implementation (i.e. they use extra space). For example, in Java, .substring(i, j) will create new String in Heap. To know more about this, please look at the source code.
- Rust provides source code in their offcial website.
- You can also look at the source code of Java via IDE.
In my opinion, the key idea of the problems is to illistrate you are able to acheive \( O(1) \) conceptually. It is not necessary to implement it so carefully.

"Extra/auxiliary space" in my definition excludes input space and output space

Code (Rust)

impl Solution {
    pub fn reverse_words(s: String) -> String {
        let space_in_u8 = 32;

        // According to RustDoc: "This consumes the `String`, so we do not need to copy its contents"
        // i.e. convert it into Vec<u8> costs O(1) Space
        let mut v = s.into_bytes();

        // i, j for sliding window,
        // k is location of cell to be filled-in
        let (mut i, mut j, mut k, n) = (0,0,0,v.len());
        while j < n {
            match (v[i] == space_in_u8, v[j]==space_in_u8){

                // Case 1: Sliding window contains only space, move two pointers
                (true, true) => {i+=1; j+=1;},

                // Impossible case
                (true, false) => {panic!("Reaches impossible case");},

                // Case 2: sliding window complete the scanning of a word
                (false, true) => {

                    // If the "current result" has some word, append space
                    if k > 0 {
                        v[k] = space_in_u8;
                        k+=1;
                    }

                    // v[k..k+j-i] = v[i..j].reverse()
                    Solution::copy_and_reverse(&mut v, i, j, &mut k);

                    // reset pointer location by right j by 1, i points to where j locates
                    j+=1;
                    i=j;
                },

                // Case 3: Sliding window contains only characters
                // It may not complete the scanning
                (false, false) => {
                    j+=1;
                    // If j reaches the end of string, do copy_and_reverse
                    if j == n {
                        if k > 0 {
                            v[k] = space_in_u8;
                            k+=1;
                        }
                        Solution::copy_and_reverse(&mut v, i, j, &mut k);
                    }
                }

            }
        }

        v.truncate(k); // cut unnecessary characters 
        Solution::reverse_string(&mut v, 0, k); // reverse the whole string

        // Convert Vec<u8> back to String
        // It costs O(1) according to String implmentation (see source code of Rust)
        // i.e. give ownership of Vec<u8> to String Struct
        return unsafe { String::from_utf8_unchecked(v) }; 
    }

    // v[k..k+j-i] = v=[i..j].reverse()
    fn copy_and_reverse(v: &mut Vec<u8>, begin: usize, end: usize, k: &mut usize){
        let k_origin = *k;

        // v[k..k+j-i] = v=[i..j]
        for i in (begin..end){
            v[*k] = v[i];
            *k +=1;
        }

        Solution::reverse_string(v, k_origin, k_origin+end-begin);
    }

    // v[k..k+j-i].reverse()
    fn reverse_string(v: &mut Vec<u8>, begin: usize, end: usize){
        let (mut i, mut j) = (begin, end - 1);
        while i < j {
            let tmp = v[i];
            v[i] = v[j];
            v[j] = tmp;
            i+=1;
            j-=1;
        }
    }
}

Complexity (\(n\) is length of the string)

Time complexity:

\( O(2n) \)
- Mirroring the whole string cost \( n / 2 \)
- Copying and mirroring a token cost \( m + m / 2 \) where m is the length of token. Since sum of the length of tokens does not exceed \(n\). The total cost less than \( 3n/2 \)
- The combined complexity is \( O(2n) \)

Auxiliary Space:

\( O(1) \)
- Depends on Programming Language and implementation
- Conceptually it can acheive O(1) Space

Further Discussion

Tags: Turing Machine

Limitation of a Programming Language and Turing Equivalence(?)

Some people argue that each language has its limitation. For instance, Java cannot actually acheive \(O(1)\) extra space in this problem.

To some extent, I will agree. Theoretically, however, if each programming language simluates Universal Turing Machine, they should be equivalent. This implies that there is no operation Rust can do but Java can't. The only matter is the cost for one language to simulate another. Just like to simulates Two-Tape Turing Machine by the One-Tape, we need more steps/operations in One-Tape Turing Machine.

Leetbook