我正在 Python 类(class)中做一些练习,其中一个我被卡住的地方如下:
Given a digit sequence that represents a message where each uppercase letter
is replaced with a number (A - 1, B - 2, ... , Z - 26) and space - 0.
Find the number of the initial messages, from which that sequence
could be obtained.
Example: 12345 - 3 (ABCDE, LCDE, AWDE)
11 - 2 (AA, K)
天真的解决方案很简单,它是简单的暴力算法:
import string
def count_init_messages(sequence):
def get_alpha(seq):
nonlocal count
if len(seq) == 0:
count += 1
return
for i in range(1, len(seq) + 1):
if seq[:i] not in alph_table:
break
else:
get_alpha(seq[i:])
alphabet = " " + string.ascii_uppercase
# generate dictionary of possible digit combination
alph_table = {str(n): alph for n, alph in zip(range(len(alphabet)), alphabet)}
# counter for the right combination met
count = 0
get_alpha(sequence)
return count
def main():
sequence = input().rstrip()
print(count_init_messages2(sequence))
if __name__ == "__main__":
main()
但是由于输入序列的长度可能长达 100 个字符并且可能有很多重复,所以我遇到了时间限制。例如,示例输入之一是 222222222222222222222222222222222222222222222222222222222222222222222(可能的消息编号为 308061521170129)
。由于我的实现重复太多,因此处理此类输入需要很长时间。我想到了回溯算法,但我还没有意识到如何实现对连续结果的内存。
如果有可能为我指出如何完成该任务的正确方法,我将非常高兴。
最佳答案
你要解决的递归关系(其中s
是一串数字,a
和b
是个位数)是这样的:
S("") = 1
S(a) = 1
S(s + a + b) = S(s+a) + (S(s) if ab is between 10 and 26)
这可以使用动态规划而不是回溯来计算。如果你做对了,它的时间复杂度为 O(n),空间复杂度为 O(1)。
def seq(s):
a1, a2 = 1, 1
for i in xrange(1, len(s)):
a1, a2 = a1 + (a2 if 9 < int(s[i-1:i+1]) < 27 else 0), a1
return a1
print seq('2222222222222222222222222222222222222222222222222222222222222222222222')
关于python - 如何应用回溯算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39811963/