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

大明大大_9498

发布时间：2024-07-12 09:40:52

492人浏览过

来源于dev.to

转载

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

问题陈述：

给定一个输入字符串 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("   ")); // ""