topcoder srm 634 div 2中的SpecialStrings探头

Question

我的python似乎可以处理不太长的输入字符串，但它不能处理很长的字符串。以下是问题陈述：

如果字符串S满足以下两个属性，则称其为特殊字符串:S中的每个字符都是'0‘或'1’。当S= UV，其中U和V都是非空字符串时，U严格小于字典顺序中的V。例如，字符串S= "00101“是特殊的，因为我们有"0”< "0101“、"00”< "101“、"001”< "01“和"0010”< "1“。你得到了一个保证是特殊的字符串电流。设N是电流的长度。考虑长度为N的所有特殊字符串的按字典排序的列表。计算并返回该列表中紧跟在current之后的字符串。如果current恰好是列表中的最后一个字符串，则返回一个空字符串。

下面是我的python代码：

class SpecialStrings(object):
    def findNext(self, current):
        if current == '0':
            return '1'
        N = len(current)
        iter_times = 2 ** N - int(current, 2) - 1
        temp_current = current
        for i in range(iter_times):
            temp_s = self.get_next_string(temp_current)
            if self.is_special(temp_s):
                return temp_s
            if temp_s[0] == '1':
                return ''
            temp_current = temp_s
        return ''

    def get_next_string(self, s):
        next_string = bin(int(s, 2) + 1)
        next_string = next_string[2:]
        if len(next_string) < len(s):
            temp_zero = '0' * (len(s) - len(next_string))
            next_string = temp_zero + next_string
        return next_string

    def is_special(self, s):
        for i in range(1, len(s)):
            left = s[:i]
            right = s[i:]
            if left >= right:
                return False
        return True

我收到异常终止，输入为“01111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111”。当我尝试用它们中的任何一个在本地测试它时，我的计算机内存耗尽了......

这里有什么问题？是不是因为我的算法效率不高？如何解决？

非常感谢！

Answer 1

您可能正在使用Python2。在Py2中，range() (第8行)返回一个列表。例如，range(3)返回0，1，2。所以range(iter_times)会创建一个占用内存的大列表。简单的解决方法:改用xrange。Refer

因为传递给xrange的参数不应该超过max signed long。例如，在我的机器中，xrange(0x7fffffff)是OK的，而xrange(0x80000000)可以触发错误。Refer

解决方法:在第8行中，使用while True:。因为如果代码按预期工作，在到达for循环的末尾之前，循环无论如何都应该返回result或空字符串。所以不需要使用for循环。

下一个问题是，当你使用'while True‘的时候，输入’011111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111这就是算法的问题。