Typescript 编码编年史：反转字符串中的单词

PHP中文网 • 2025年3月7日 13:41:37 • 编程技术 • 阅读 2

问题陈述：

给定一个输入字符串 s，反转单词的顺序。单词被定义为非空格字符的序列。 s 中的单词将至少由一个空格分隔。返回由单个空格按相反顺序连接的单词字符串。

注意 s 可能包含前导或尾随空格或两个单词之间的多个空格。返回的字符串应该只有一个空格来分隔单词。请勿包含任何多余空格。

示例1：

输入：s =“天空是蓝色的”输出：“蓝色是天空”

示例2：

输入：s =“你好世界”输出：“世界你好”说明：您的反转字符串不应包含前导或尾随空格。

示例3：

输入：s =“一个很好的例子”输出：“例子很好”说明：您需要将两个单词之间的多个空格减少为反转字符串中的单个空格。

限制条件：

1 s 包含英文字母（大小写）、数字和空格 ‘ ‘.s中至少有一个单词

初步思考过程：

要解决这个问题，我们需要：

将字符串拆分成单词。颠倒单词的顺序。将单词重新连接在一起，每个单词之间有一个空格。

基本解决方案：

代码：

function reversewordsbruteforce(s: string): string {    // split the string by spaces and filter out empty strings    let words = s.trim().split(/s+/);    // reverse the array of words    words.reverse();    // join the words with a single space    return words.join(' ');}

登录后复制

时间复杂度分析：

时间复杂度： o(n)，其中n是字符串的长度。分裂、反转和合并都需要线性时间。空间复杂度： o(n)，其中n是字符串的长度。我们将单词存储在数组中，将最终结果存储在字符串中。

限制：

考虑到限制，这个解决方案是有效的。但是，它为单词数组使用了额外的空间。

优化方案：

如果字符串数据类型是可变的，并且我们需要使用 o(1) 额外空间就地解决它，我们可以使用两指针技术来反转原始字符串中的单词。

代码：

function reversewordsoptimized(s: string): string {    // trim the string and convert it to an array of characters    let chars = s.trim().split('');    // helper function to reverse a portion of the array in place    function reverse(arr: string[], left: number, right: number) {        while (left < right) {            [arr[left], arr[right]] = [arr[right], arr[left]];            left++;            right--;        }    }    // reverse the entire array of characters    reverse(chars, 0, chars.length - 1);    // reverse each word in the reversed array    let start = 0;    for (let end = 0; end <= chars.length; end++) {        if (end === chars.length || chars[end] === ' ') {            reverse(chars, start, end - 1);            start = end + 1;        }    }    // join the characters back into a string and split by spaces to remove extra spaces    return chars.join('').split(/s+/).join(' ');}

登录后复制

时间复杂度分析：

时间复杂度： o(n)，其中n是字符串的长度。每个字符都会被处理固定次数。空间复杂度： o(1)，因为我们正在就地修改数组并仅使用恒定量的额外空间。

基本解决方案的改进：

优化的解决方案通过对字符数组执行就地操作来降低空间复杂度。

边缘情况和测试：

边缘情况：

字符串包含前导空格和尾随空格。字符串中单词之间包含多个空格。该字符串仅包含一个单词。字符串长度达到最小或最大限制。

测试用例：

console.log(reverseWordsBruteForce("the sky is blue")); // "blue is sky the"console.log(reverseWordsBruteForce("  hello world  ")); // "world hello"console.log(reverseWordsBruteForce("a good   example")); // "example good a"console.log(reverseWordsBruteForce("singleWord")); // "singleWord"console.log(reverseWordsBruteForce("   ")); // ""console.log(reverseWordsOptimized("the sky is blue")); // "blue is sky the"console.log(reverseWordsOptimized("  hello world  ")); // "world hello"console.log(reverseWordsOptimized("a good   example")); // "example good a"console.log(reverseWordsOptimized("singleWord")); // "singleWord"console.log(reverseWordsOptimized("   ")); // ""

登录后复制