Hyper Strings InterviewStreet: Python

Question

https://www.interviewstreet.com/challenges/dashboard/#problem/4f802ebfad2a1
Mon code réussit 6/10 cas de test.

from collections import Counter 
j,k = map(int, raw_input().split()) 

y = Counter(len(raw_input()) for i in range(j)) 

saved = {} 

def f(x): 
    if x in saved: return saved[x] 
    if x<1: return 0 
    k = y[x] if x in y else 0 
    for i in y: 
     k += y[i]*f(x-i) 
    saved[x] = k 
    return k 
x = 0 
for i in xrange(1,k+1): 
    x+=f(i) 

print (x+1)%1000000007 

Entrez « y » est la longueur de super chaîne et sa valeur est le nombre de chaînes de super avec cette longueur dans le jeu « H ».

poignées 'sauvé' memoization.

f (x) calcule les chaînes hyper de longueur x. Je parcourt toutes les valeurs dans la dernière boucle for.

x a un résultat, sauf chaîne vide (« »), donc x + 1

Answer 1

Je pense que ce code échoue dans les cas où une chaîne super est concat de toute autre chaîne super. Dans ce cas, ce code ajoutera plusieurs cas plusieurs fois. Par exemple:

3 2 
a 
b 
ab 

Votre sortie: 8
Sortie droite: 7
double comptage des "ab"
Je suis moi-même essayer la question, affichera la réponse dans le cas où elle marque 10/10

Answer 2

OK, voici mon code. J'ai utilisé votre code comme algorithme, mais j'ai retiré les super-chaînes qui peuvent être formées par concaténation d'autres super-chaînes. Merci d'avoir posté votre problème, mon code d'origine avant de voir ce post était terriblement non-optimal. Toute suggestion pour optimiser davantage ceci est la bienvenue.

from collections import Counter 
j,k = map(int, raw_input().split()) 

supers_list = [] 

for i in range(j): 
    supers_list.append(raw_input()) 

def check_concat(Str_, Sub_Str_): 
    if Sub_Str_ == "": 
     return False 

    for i in supers_list: 
     if i == Sub_Str_ and Str_ != Sub_Str_: 
     return True 
    x = Sub_Str_.startswith(i) 
    if x == True: 
     if check_concat(Str_, Sub_Str_[len(i):]) == True: 
      return True 
return False 

def filter_(): 
    tmp = [] 
    global supers_list 
    for i in supers_list: 
     if check_concat(i,i) == False: 
      tmp.append(i) 
    supers_list = tmp 

filter_() 

y = Counter(len(i) for i in supers_list) 

saved = {} 

def f(x): 
    if x in saved: return saved[x] 
    if x<1: return 0 
    k = y[x] if x in y else 0 
    for i in y: 
     k += y[i]*f(x-i) 
    saved[x] = k 
    return k 
x = 0 
for i in xrange(1,k+1): 
    x+=f(i) 

print (x+1)%1000000007