翻转单词序列

题目描述

示例

代码

代码1 偷懒的写法，先按空格转数组，再将数组翻转，在转字符串

function ReverseSentence(str)
{
    if(str === '') return ''
    
    return str.split(' ').reverse().join(' ')
}

代码2 正常解法，字符串转数组，先翻转整个数组，开始找空格，再依次翻转里面的单词

/*
1. 先翻转整个字符串，并用两个指针变量记录某个单词的首尾，去寻找空格，
2. 当尾部碰到空格，就说明现在记录的范围内的单词需要再翻转，翻转过后，重新维护两个指针。
重复 1 2
*/
function ReverseSentence(str)
{
    if(str === null || str === '') return str
    
    // 1.将字符串转数组，先全部翻转
    let arr = str.split('')
    reverseArr(arr, 0, arr.length-1)
    
    let start = 0 // 指向单词的第一个字母
    let end = 0 // 指向单词的最后一个字母
    
    while(start < arr.length){
        if(arr[start] === ' '){
            // 如果 start 指向的是空格，就换下一个，因为指针要指向单词
            start++
            end++
        } else if(end === arr.length || arr[end] === ' ') {
            // 要么尾部是空格，要么end刚刚超过数组的最后一个角标
            // 这两种情况就应该翻转了
            // end之所以会超过最后角标，是因为当最后一个字符不是空格时，会让end++，所以会越界
            reverseArr(arr, start, end-1)
            // 翻转后 应该重新记录下个单词，更新 start和end
            end++
            start = end
        } else {
            // 这里说明，start指的不是空格， end指的也不是空格，说明是正常单词，end++即可
            end++
        }
    }
    
    return arr.join('')
    
    
    // 翻转数组，直接在原数组操作，传入开始索引和结束索引
    function reverseArr(arr, begin, end){
        while(begin < end){
            let temp = arr[begin]
            arr[begin] = arr[end]
            arr[end] = temp
            
            begin++
            end--
        }
    }
}

时间复杂度O(n)

空间复杂度O(n)

题目来源

JZ73 翻转单词序列