1

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'中具有该长度的超级字符串的数量。

'已保存' 处理记忆。

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

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

4

2 回答 2

2

我认为在任何超级字符串与任何其他超级字符串连接的情况下，此代码都会失败。在这种情况下，这段代码会多次添加一些案例。例如：

3 2
a
b
ab

您的输出：8
正确输出：7
“ab”的双重计数
我自己正在尝试这个问题，如果它得分 10/10，将发布答案

于 2012-09-25T17:15:36.657 回答
1

好的，这是我的代码。我已将您的代码用作算法，但删除了可以通过连接其他超级字符串形成的超级字符串。感谢您发布您的问题，我在看到这篇文章之前的原始代码非常不理想。欢迎任何进一步优化这一点的建议。

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
于 2012-09-26T11:44:05.270 回答