python - 计算在给定映射的情况下可以解码消息的方式的数量

Question

所以我正在尝试制作一个程序，打印出一条消息可以被解码的方式的数量。在代码本身中可以很容易地理解映射。现在它适用于大多数数字，但对于某些数字它计算不正确。例如数字 1111，它的解法好像有 2 种解码方式，但实际上有 4 种不同的解码方式。

这是我的代码:

mapping=["1", "2", "3", "4", "5", "6", "7" "8", "9", "10", "11", "12", "13", "14", "15", "16", "17", "18", "19", "20", "21", "22", "23", "24", "25", "26"]

encodedCases = ["918", "739", "1142", "56", "82", "118", "1219", "6", "862", "1111"]

def decodeNumber(test, mapping):
    count=0
    checkFirstLast=0
    for i in range(9, len(mapping)):
        if mapping[i] in test:
            count+=1
        if test[:2]!=test[-2:]:
            if len(test)>3 and mapping[i] in test[:2]:
                checkFirstLast+=1
            elif len(test)>3 and mapping[i] in test[-2:]:
                checkFirstLast+=1

    if checkFirstLast==2:
        count+=1
    print count + 1

for test in encodedCases:
    test = test.strip()
    decodeNumber(test, mapping)

使用这种方法我还没有找到能够成功正确计算的方法。有没有更好的方法来实现这一目标？提前致谢!

注意 - 映射是字母表的表示，为每个字母提供其在字母表中的位置值。

Answer 1

我可以想到一种递归方法:

def decodeNumber(test):
    if not test: # check if test is empty
        return 1

    count = 0

    for i in mapping:
        if test.startswith(i):
            count += decodeNumber(test[len(i):])

    return count


for test in encodedCases:
    test = test.strip()
    print test, "==>" , decodeNumber(test)

decodeNumer 检查 test 输入是否以映射中的条目开头。对于所有执行此操作的条目，它都会调用自己。新参数是 test[len(i):]，这意味着 test 从开头删除了条目。

例如让 test = "918":当 i == "9" 并且新参数是 时，if 语句第一次评估为 true >test[len("9"):] 等于“18”。

总计数计算为消耗完整输入的路径总数。