Typescript コーディング クロニクル: 文字列内の単語を反転する

問題の説明:

入力文字列 s を指定して、単語の順序を逆にします。単語は、スペース以外の文字のシーケンスとして定義されます。 s 内の単語は少なくとも 1 つのスペースで区切られます。単一のスペースで連結された単語の文字列を逆順で返します。

s には、先頭または末尾のスペース、または 2 つの単語の間に複数のスペースが含まれる場合があることに注意してください。返される文字列には、単語を区切るスペースが 1 つだけ含まれている必要があります。余分なスペースは含めないでください。

例 1:

• 入力: s = "空は青い"
• 出力: 「青は空です」

例 2:

• 入力: s = " hello world "
• 出力: 「ワールドハロー」
• 説明: 反転文字列には先頭または末尾のスペースを含めることはできません。

例 3:

• 入力: s = "良い例"
• 出力: 「良い例」
• 説明: 反転文字列では、2 つの単語の間にある複数のスペースを 1 つのスペースに減らす必要があります。

制約:

• 1
• s には、英字 (大文字と小文字)、数字、およびスペース「 」が含まれます。
• s には少なくとも 1 つの単語があります。

最初の思考プロセス:

この問題を解決するには、次のことを行う必要があります:

1. 文字列を単語に分割します。
2. 単語の順序を逆にします。
3. 各単語の間にスペースを 1 つ入れて、単語を結合します。

基本的な解決策:

コード：

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) 個の追加スペースを使用してその場で解決する必要がある場合は、2 ポインター手法を使用して、元の文字列内の単語を反転できます。

コード：

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)。配列を適切に変更し、一定量の追加スペースのみを使用しているためです。

基本的なソリューションの改善点:

• 最適化されたソリューションは、文字の配列に対してインプレース操作を実行することにより、スペースの複雑さを軽減します。

エッジケースとテスト:

エッジケース:

1. 文字列には先頭と末尾のスペースが含まれています。
2. 文字列には単語の間に複数のスペースが含まれています。
3. 文字列には単語が 1 つだけ含まれています。
4. 文字列の長さが最小または最大制限に達しています。

テストケース:

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("   ")); // ""

一般的な問題解決戦略:

1. 問題を理解する: 問題の説明を注意深く読み、要件と制約を理解します。
2. キー操作の特定: 単語の分割、反転、結合など、必要なキー操作を決定します。
3. 読みやすさを最適化する: 明確かつ簡潔なロジックを使用して、コードを理解しやすくします。
4. 徹底的にテストします: エッジケースを含むさまざまなケースでソリューションをテストし、正確さを確認します。

同様の問題を特定する:

1. 文字列操作:

   • 特定の条件に基づいて文字列を変更する必要がある問題。
   • 例: 文の各単語の文字の順序を逆にする。

2. ツーポイントテクニック:

   • 2 つのポインターを使用すると解の最適化に役立つ問題。
   • 例: ソートされた配列から重複を削除します。

3. インプレースアルゴリズム:

   • 限られた追加スペースで操作を適切な場所で実行する必要がある問題。
   • 例: 配列を右に k ステップ回転します。

結論：

• 文字列内の単語を反転する問題は、総当たりアプローチと最適化されたインプレース アプローチの両方を使用して効率的に解決できます。
• 問題を理解し、管理可能な部分に分割することが重要です。
• 明確なロジックを使用し、読みやすさを最適化することで、ソリューションは理解しやすくなります。
• さまざまなエッジケースでのテストにより、堅牢性が保証されます。
• 問題のパターンを認識すると、同様の解決策を他の課題に適用するのに役立ちます。

このような問題と戦略を実践することで、問題解決スキルを向上させ、さまざまなコーディングの課題に対する準備を整えることができます。

以上がTypescript コーディング クロニクル: 文字列内の単語を反転するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。