-3

我有这个程序来形成一组从字符串集合中按字典顺序排列的字符串。输入字符串的数量和字符串本身作为输入，程序旨在按字典顺序形成一个包含来自输​​入的字符串和子字符串的集合。

strst=set()
nos=input()

for i in range(0,nos):
    ele=raw_input()
    for j in range(0,len(ele),1):
        for k in range(j+1,len(ele)+1):
                strst.add(ele[j:k])

strlst=sorted(strst)

print strlst

这个程序将子字符串存储到一个集合中，然后按照字典顺序对其进行排序，最后打印整个列表

例如：

INPUT :

2             //number of input strings
aab
aac

OUTPUT

['a', 'aa', 'aab', 'aac', 'ab', 'ac', 'b', 'c']

该程序适用于小型输入，但是当输入大小（即输入字符串的数量和每个字符串的长度）在 2000 范围内增加时，它会给出异常：

MemoryError thrown on line 9

我想我还没有优化代码。排序可以优化吗？..集合数据结构和列表的大小可以扩展吗？

4

2 回答 2

0

说它似乎是多余的，我怀疑您遇到内存错误的原因是您的内存不足。

如果有 2 个大部分重叠的长度为 3 的字符串，你会得到 8 个元素，那么只有所有可能的 3 个字母的非空白覆盖 = 26 + 650 + 15600 = 16276

作为快速测试：

>>> n = 0
>>> for m in range(1, 20):
...     for i in itertools.permutations(range(26), m):
...         n+=1
...     print m, n
... 
1 26
2 676
3 16276
4 375076
5 8268676
6 174034276

……

于 2013-07-28T08:15:14.050 回答
0

正如史蒂夫正确指出的那样，问题是输入字符串的组合数，即您是内存中的字符串。

正确的解决方案是使用生成器函数来生成输入字符串的组合。

幸运的是，python 标准库已经包含itertools包，它可以帮助您以更少的代码和更有效的方式实现您想要的。下面给出的是一个示例代码片段，它将产生与您在问题中作为示例显示的相同输出：

import itertools
from itertools import combinations
x  = "aab"
y =  "aac"
x_permutation =[]
y_permutation = []

#use the combinations method within the itertools package to generate all possible combinations of a given length  for a given string

for i in xrange(1,len(x)+1):
        x_permutation = x_permutation + list(map("".join,combinations(x,i)))

for i in xrange(1,len(y)+1):
        y_permutation = y_permutation + list(map("".join, combinations(y,i)))

#if the input string is  already sorted for e.g. "ABCD" , you do not really need to call the sort.However, when we do not have this guarantee then it is better to call sort()

x_permutation.sort()
y_permutation.sort()

#merge the two lists into a set and then sort the set using the built-in **sorted()**
output_set =sorted(set (x_permutation + y_permutation))

print output_set

上述脚本的输出是：['a', 'aa', 'aab', 'aac', 'ab', 'ac', 'b', 'c']

希望这现在应该可以帮助您考虑使用 itertools 技术解决您的问题。

于 2013-07-28T09:15:29.957 回答