Problème:

Terminez la fonction scramble (str1, str2) qui renvoie true si une partie des caractères str1 peut être réorganisée pour correspondre à str2, sinon renvoie false.

Remarques:

  • Seules les lettres minuscules seront utilisées (a-z). Aucune ponctuation ou chiffres ne seront inclus.
  • La performance doit être prise en compte

Je pourrais résoudre ce problème en C. Comme je suis intéressé par l'apprentissage de Python, j'ai essayé de le faire également en Python, mais j'ai malheureusement eu une erreur de temporisation. Je ne sais pas comment le résoudre en Python de la même manière que je l'ai fait en C.

Alors, dites-moi comment puis-je faire cela efficacement en Python, de préférence avec la même technique ou une meilleure technique que j'ai utilisée avec C.

#include <stdbool.h>

bool scramble(const char* str1, const char* str2)
{
    // store number of occurrences of each character in str1 to arr
    int arr[26] = { 0 };

    while (*str1) {
        arr[*str1 - 'a'] += 1;
        str1++;
    }

    // check if each character of str2 is in arr
    while (*str2) {

        if (arr[*str2 - 'a'] >= 1)
            arr[*str2 - 'a'] -= 1;
        else
            return false;

        str2++;
    }

    return true;
}

Mon code Python qui est probablement correct mais expire:

def scramble(s1, s2):
    text = list(s1)

    for char in s2:
        try:
            text.remove(char)
        except ValueError:
            return False

    return True

De plus, si vous trouvez quelque chose qui ne va pas avec mon code C, veuillez m'en informer.

PS: désolé pour mon anglais.

-2
lightsaber 19 avril 2020 à 03:53

2 réponses

Meilleure réponse

Comme je pense que vous êtes très nouveau sur Python. Pour en savoir plus sur la collection: https://www.google.com/url?sa=t&source=web&rct=j&url=https://docs.python.org/2/library/collections.html&ved=2ahUKEwj9wICRqfPoAhVo73MBHRcBAq8QFjAAegQIBBAC&usg = AOvVaw2mS2EUGTioSwy05lVk67KH

defaultdict est une méthode de package / bibliothèque collections qui initialise la structure de données avec une valeur initiale. Exemple:

import collections
counter = collections.defaultdict(int)
print(counter[ANY_KEY])
print(counter)

Production:

0
{ANY_KEY: 0}

Ainsi, puisque nous avons donné defaultdict(int) c'est-à-dire int , la définition d'une clé sera toujours initialisée avec la valeur indiquée entre parenthèses

import collections
def scramble(s1, s2):
    counter = collections.defaultdict(int)

    for char in s1:
        counter[char]+=1
    for char in s2:
         counter[char]-=1
         if counter[char] <= -1:
             return False
    return True
0
Dhruv Agarwal 19 avril 2020 à 01:47

Le problème n'est pas Try Except que votre algorithme est de complexité quadratique, qui commencera à se désagréger à mesure que les chaînes deviendront très grandes. Pour chaque caractère de s2, vous devez parcourir s1. Le site code wars exécute des tests pour les chaînes de 600 000 caractères maximum. Un algorithme O (n ^ 2) va poser problème ici.

Voici une option qui sera plus lente sur les petites chaînes, mais qui s'adapte mieux aux grandes chaînes:

from collections import Counter

def scramble(s1, s2):
    c1 = Counter(s1)
    c2 = Counter(s2)
    return all(c1.get(k, 0) >= s for k, s in c2.items())

Cela fonctionne en effectuant un seul passage dans chaque chaîne pour obtenir les décomptes, puis un autre passage à tester. Il passe tous les tests sur le site des codewars.

0
Mark M 19 avril 2020 à 01:15