Typescript 編碼編年史：反轉字串中的單字-js教程-PHP中文網

Typescript 編碼編年史：反轉字串中的單字

PHPz

發布： 2024-07-18 18:03:28

原創

585 人瀏覽過

Typescript Coding Chronicles: Reverse Words in a String

問題陳述：

給定一個輸入字串 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("   ")); // ""

登入後複製