Reverse all words in a string

Posted on | In | Comments: | Views:

I. Problem

Given a string consisted of several words, reverse all words in this string.

Note:

  1. you need to trim starting & trailing white space
  2. reduce multiple spaces to only on space between each word
1
2
3
"   This is a    test   string  " 
  ==> 
"string test a is This"

II. Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
// Test
let str = "   This is a test   string"
let res = reverseString(str)
console.log(res)	   		// "string test a is This"

str = "This    "
res = reverseString(str) 
console.log(res)	   		// "This"

str = "This is  "
res = reverseString(str) 
console.log(res)	   		// "is This"

str = "This"
res = reverseString(str) 
console.log(res)	   		// "This"

str = ""
res = reverseString(str) 
console.log(res)	   		// ""

str = "  "
res = reverseString(str) 
console.log(res)	   		// ""


function reverseString  (str){
    let arr = str.trim().split(/\s+/)
    let n = arr.length
    
    reverse(arr, 0, n-1)
    let start = 0
    let end = 0
    for( let i = 1; i < n; i++ ){
        let prevChar = arr[i-1]
        let currChar = arr[i]
        if( prevChar !== ' ' && currChar === ' ' ){
            end = i-1
            reverse(arr, start, end)
        }else if( prevChar === ' ' && currChar !== ' ' ){
            start = i
        }else{
            continue
        }
    }
    if(start!==0) reverse(arr, start, n-1)
    return arr.join(' ')
}

function reverse (arr, left, right){
    while( left < right ){
        [arr[left], arr[right]] = [arr[right], arr[left]]
        left++
        right--
    }
}

III. Complexity

  1. Time: O(N)
  2. Space: O(N)