Chaîne super réduite en python

Question

J'ai eu des problèmes avec cette simple question de hackerrank. Mon code fonctionne dans le compilateur mais le test hackerrank échoue à 6 cas de test. L'un d'entre eux est correct (je n'ai pas payé de prime). Y a-t-il quelque chose qui ne va pas ici ?

Prompt : Steve a une chaîne de caractères minuscules dans l'intervalle ascii['a'..'z']. Il souhaite réduire la chaîne à sa plus petite longueur en effectuant une série d'opérations au cours desquelles il sélectionne une paire de lettres minuscules adjacentes qui correspondent, puis il les supprime. Par exemple, la chaîne aab peut être réduite à b en une seule opération.

La tâche de Steve consiste à supprimer autant de caractères que possible à l'aide de cette méthode et à imprimer la chaîne de caractères obtenue. Si la chaîne finale est vide, il faut imprimer Chaîne vide

Ex.

aaabccddd → abccddd → abddd → abd

baab → bb → Chaîne vide

Voici mon code :

def super_reduced_string(s):
    count_dict = {}
    for i in s:
        if (i in count_dict.keys()):
            count_dict[i] += 1 
        else:
            count_dict[i] = 1 

    new_string = ''
    for char in count_dict.keys():
        if (count_dict[char] % 2 == 1):
            new_string += char

    if (new_string is ''):
        return 'Empty String'
    else:
        return new_string

Voici un exemple de sortie pour laquelle cela ne fonctionne pas.

print(super_reduced_string('abab'))

Il produit 'Empty String' mais devrait produire 'abab' .

Answer 1

En utilisant un compteur, votre programme perd la trace de l'ordre dans lequel il a vu les caractères. Par exemple, avec l'entrée 'abab' , vous programmez voit deux a et deux b et les supprime même si elles ne sont pas adjacentes. Il produit ensuite 'Empty String' mais devrait produire 'abab' .

O(n) solution basée sur une pile de données

Ce problème est équivalent à la recherche de parenthèses non appariées, mais où un caractère d'ouverture est son propre caractère de fermeture.

Cela signifie qu'il peut être résolu en une seule traversée à l'aide d'une pile.

Puisque Python peut renvoyer une chaîne vide, nous allons l'afficher à la place de 'Empty String' qui pourrait être ambiguë si on lui donnait une entrée telle que 'EEEmpty String' .

Código

def super_reduced_string(s):
    stack = []
    for c in s:
        if stack and c == stack[-1]:
            stack.pop()
        else:
            stack.append(c)

    return ''.join(stack)

Tests

print(super_reduced_string('aaabab'))     # 'abab'
print(super_reduced_string('aabab'))      # 'bab'
print(super_reduced_string('abab'))       # 'abab'
print(super_reduced_string('aaabccddd ')) # 'abd'
print(super_reduced_string('baab '))      # ''

Answer 2

J'ai résolu le problème à l'aide de la récursivité :

def superReducedString(s):
    if not s:
        return "Empty String"
    for i in range(0,len(s)):
        if i < len(s)-1:
            if s[i] == s[i+1]:
                return superReducedString(s[:i]+s[i+2:])
    return s

Ce code parcourt la chaîne de caractères et vérifie si la lettre/position actuelle et la suivante sont identiques. Si c'est le cas, ces deux lettres/positions sont supprimées de la chaîne et la nouvelle chaîne réduite est transmise à la fonction. Cela se produit jusqu'à ce qu'il n'y ait plus de paires dans la chaîne.

TESTS :

print(super_reduced_string('aaabccddd')) # 'abd'
print(super_reduced_string('aa')) # 'Empty String'
print(super_reduced_string('baab')) # 'Empty String'

Answer 3

J'ai résolu le problème en créant une liste, puis en ajoutant uniquement les lettres uniques et en supprimant la dernière lettre trouvée dans la chaîne principale. Finalement, tous les tests ont été réussis !

def superReducedString(self, s):
    stack = []
    for i in range(len(s)):
        if len(stack) == 0 or s[i] != stack[-1]:
            stack.append(s[i])
        else:
            stack.pop()
    return 'Empty String' if len(stack) == 0 else ''.join(stack)