当前位置：首页 > article >正文

数据结构与算法之栈: LeetCode 151. 反转字符串中的单词 (Ts版)

article 2025/1/15 11:20:58

反转字符串中的单词

https://leetcode.cn/problems/reverse-words-in-a-string/

描述

给你一个字符串 s ，请你反转字符串中单词的顺序
单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开
返回单词顺序颠倒且单词之间用单个空格连接的结果字符串
注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格
返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格

示例 1

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2

输入：s = "  hello world  "
输出："world hello"

解释：反转后的字符串中不能存在前导空格和尾随空格

示例 3

输入：s = "a good   example"
输出："example good a"

解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示

1 <= s.length <= $10^4$
s 包含英文大小写字母、数字和空格 ’ ’
s 中至少存在一个单词
进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的原地解法

Typescript 版算法实现

1 ) 方案1: 使用语言特性

function reverseWords(s: string): string {
    return s.trim().split(/\s+/).reverse().join(' ');
};

2 ) 方案2: 自行编写对应的函数

function trimSpaces(s: string): string[] {
    let left = 0, right = s.length - 1;
    
    // 去掉字符串开头的空白字符
    while (left <= right && s[left] === ' ') {
        left++;
    }
    
    // 去掉字符串末尾的空白字符
    while (left <= right && s[right] === ' ') {
        right--;
    }
    
    // 将字符串间多余的空白字符去除
    const output: string[] = [];
    while (left <= right) {
        if (s[left] !== ' ') {
            output.push(s[left]);
        } else if (output.length > 0 && output[output.length - 1] !== ' ') {
            output.push(s[left]);
        }
        left++;
    }
    
    return output;
}

function reverse(l: string[], left: number, right: number): void {
    while (left < right) {
        [l[left], l[right]] = [l[right], l[left]];
        left++;
        right--;
    }
}

function reverseEachWord(l: string[]): void {
    const n = l.length;
    let start = 0, end = 0;
    
    while (start < n) {
        // 循环至单词的末尾
        while (end < n && l[end] !== ' ') {
            end++;
        }
        // 翻转单词
        reverse(l, start, end - 1);
        // 更新start，去找下一个单词
        start = end + 1;
        end = start;
    }
}

function reverseWords(s: string): string {
    const l = trimSpaces(s);
    
    // 翻转字符串
    reverse(l, 0, l.length - 1);
    
    // 翻转每个单词
    reverseEachWord(l);
    
    return l.join('');
}

3 ) 方案3: 双端队列

function reverseWords(s: string): string {
    let left = 0, right = s.length - 1;
    
    // 去掉字符串开头的空白字符
    while (left <= right && s[left] === ' ') {
        left++;
    }
    
    // 去掉字符串末尾的空白字符
    while (left <= right && s[right] === ' ') {
        right--;
    }
    
    const words: string[] = [];
    let word: string[] = [];
    
    // 将单词 push 到数组中
    while (left <= right) {
        if (s[left] === ' ' && word.length > 0) {
            words.unshift(word.join(''));
            word = [];
        } else if (s[left] !== ' ') {
            word.push(s[left]);
        }
        left++;
    }
    
    // 添加最后一个单词
    if (word.length > 0) {
        words.unshift(word.join(''));
    }
    
    return words.join(' ');
}