Chroniques de codage dactylographié : inverser les mots dans une chaîne

Énoncé du problème :

Étant donné une chaîne d'entrée s, inversez l'ordre des mots. Un mot est défini comme une séquence de caractères autres que des espaces. Les mots entre s seront séparés par au moins un espace. Renvoie une chaîne de mots dans l'ordre inverse concaténés par un seul espace.

Notez que les s peuvent contenir des espaces de début ou de fin ou plusieurs espaces entre deux mots. La chaîne renvoyée ne doit comporter qu’un seul espace séparant les mots. N'incluez aucun espace supplémentaire.

Exemple 1 :

• Entrée : s = "le ciel est bleu"
• Sortie : "le bleu est le ciel"

Exemple 2 :

• Entrée : s = " bonjour tout le monde "
• Sortie : "bonjour le monde"
• Explication : Votre chaîne inversée ne doit pas contenir d'espaces de début ou de fin.

Exemple 3 :

• Entrée : s = "un bon exemple"
• Sortie : "exemple bon a"
• Explication : Vous devez réduire plusieurs espaces entre deux mots à un seul espace dans la chaîne inversée.

Contraintes :

• 1 <= s.length <= 10^4
• s contient des lettres anglaises (majuscules et minuscules), des chiffres et des espaces ' '.
• Il y a au moins un mot dans s.

Processus de réflexion initial :

Pour résoudre ce problème, nous devons :

1. Divisez la chaîne en mots.
2. Inversez l'ordre des mots.
3. Rejoignez les mots avec un seul espace entre chacun.

Solution de base :

Code:

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(' ');
}

Analyse de la complexité temporelle :

• Complexité temporelle : O(n), où n est la longueur de la chaîne. Le fractionnement, l'inversion et la jointure prennent tous un temps linéaire.
• Complexité spatiale : O(n), où n est la longueur de la chaîne. Nous stockons les mots dans un tableau et le résultat final dans une chaîne.

Limites:

Cette solution est efficace compte tenu des contraintes. Cependant, il utilise un espace supplémentaire pour le tableau de mots.

Solution optimisée :

Si le type de données chaîne est mutable et que nous devons le résoudre sur place avec un espace supplémentaire O(1), nous pouvons utiliser une technique à deux pointeurs pour inverser les mots dans la chaîne d'origine.

Code:

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(' ');
}

Analyse de la complexité temporelle :

• Complexité temporelle : O(n), où n est la longueur de la chaîne. Chaque caractère est traité un nombre constant de fois.
• Complexité spatiale : O(1), car nous modifions le tableau en place et n'utilisons qu'une quantité constante d'espace supplémentaire.

Améliorations par rapport à la solution de base :

• La solution optimisée réduit la complexité de l'espace en effectuant des opérations sur place sur le tableau de caractères.

Cas extrêmes et tests :

Cas extrêmes :

1. La chaîne contient des espaces de début et de fin.
2. La chaîne contient plusieurs espaces entre les mots.
3. La chaîne ne contient qu'un seul mot.
4. La longueur de la chaîne est à la limite minimale ou maximale.

Cas de tests :

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

Stratégies générales de résolution de problèmes :

1. Comprendre le problème : Lisez attentivement l'énoncé du problème pour comprendre les exigences et les contraintes.
2. Identifier les opérations clés : Déterminez les opérations clés nécessaires, telles que le fractionnement, l'inversion et la jointure de mots.
3. Optimiser pour la lisibilité : Utilisez une logique claire et concise pour garantir que le code est facile à suivre.
4. Testez minutieusement : Testez la solution avec divers cas, y compris les cas extrêmes, pour garantir son exactitude.

Identifier des problèmes similaires :

1. Manipulation de chaînes :

   • Problèmes pour lesquels vous devez modifier des chaînes en fonction de conditions spécifiques.
   • Exemple : Inverser l'ordre des caractères dans chaque mot d'une phrase.

2. Technique à deux pointeurs :

   • Problèmes pour lesquels l'utilisation de deux pointeurs peut aider à optimiser la solution.
   • Exemple : Suppression des doublons d'un tableau trié.

3. Algorithmes sur place :

   • Problèmes où les opérations doivent être effectuées sur place avec un espace supplémentaire limité.
   • Exemple : Rotation d'un tableau vers la droite de k pas.

Conclusion:

• Le problème de l'inversion des mots dans une chaîne peut être résolu efficacement en utilisant à la fois une approche par force brute et une approche optimisée sur place.
• Comprendre le problème et le décomposer en parties gérables est crucial.
• L'utilisation d'une logique claire et l'optimisation pour la lisibilité garantissent que la solution est facile à suivre.
• Les tests avec différents cas extrêmes garantissent la robustesse.
• Reconnaître les schémas des problèmes peut aider à appliquer des solutions similaires à d'autres défis.

En pratiquant de tels problèmes et stratégies, vous pouvez améliorer vos compétences en résolution de problèmes et être mieux préparé à relever divers défis de codage.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!