python - 超弦 InterviewStreet : Python

Question

https://www.interviewstreet.com/challenges/dashboard/#problem/4f802ebfad2a1
我的代码通过了 6/10 个测试用例。

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

'y'中的键是超字符串的长度，它的值是集合'H'中具有该长度的超字符串的数量。

'saved' 处理内存。

f(x) 计算长度为 x 的超字符串。我遍历最后一个“for 循环”中的所有值。

x 有除空字符串 ('') 之外的结果，因此 x+1

Answer 1

我认为当任何 super 字符串是任何其他 super 字符串的连接时，这段代码会失败。在这种情况下，这段代码会多次添加一些案例。例如:

3 2
a
b
ab

你的输出:8
右输出:7
重复计算“ab”
我自己正在尝试这个问题，如果得分为 10/10，我会发布答案