解码字符串算法实现的建议

Question

解码字符串算法实现的建议

pythonalgorithm

3

以下是一道解密数字字符串的算法题，需要将数字转化为相应字符。请提供完整的问题描述和参考代码。我查阅了一些解决方案，发现所有的解码方法都是从后往前解码，但我认为也可以从前往后解码，请问从后往前解码有什么特殊的优势或者考虑因素吗？谢谢。

给定一个由字母 A-Z 组成的消息，使用下列映射将其编码为数字：

'A' -> 1 'B' -> 2 ... 'Z' -> 26

给定一个包含数字的编码消息，确定总共有多少种解码方式。

例如，给定编码消息 "12"，它可以解码为 "AB" (1 2) 或者 "L" (12)。

解码 "12" 的方法有 2 种。

public class Solution {
    public int numDecodings(String s) {
        int n = s.length();
        if (n == 0) return 0;

        int[] memo = new int[n+1];
        memo[n]  = 1;
        memo[n-1] = s.charAt(n-1) != '0' ? 1 : 0;

        for (int i = n - 2; i >= 0; i--)
            if (s.charAt(i) == '0') continue;
            else memo[i] = (Integer.parseInt(s.substring(i,i+2))<=26) ? memo[i+1]+memo[i+2] : memo[i+1];

        return memo[0];
    }
}

thanks in advance, Lin

- Lin Ma

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Termi · Accepted Answer

如果你将字符串分成子字符串并存储它们的结果，从前往后或从后往前解码字符串没有区别。

以下实现了从前往后的方法：

def decode_string(st):
    result_dict = {st[0]:1}

    for i in xrange(2,len(st)+1):
        if int(st[i-1]) == 0:
            if int(st[i-2]) not in [1,2]:
                return "Not possible to decode"

            result_dict[st[:i]] = 0

        else:
            result_dict[st[:i]] = result_dict[st[:i-1]]

        if int(st[i-2:i]) < 27 and st[i-2] != '0':
            result_dict[st[:i]] = result_dict[st[:i]] + result_dict.get(st[:i-2],1)

    return result_dict[st]

print decode_string("125312")

result_dict 包含所有增量子字符串的可能性。初始化为第一个字符。

特殊检查 '0' 字符，因为 0 的唯一可接受值是 10 和 20。如果输入包含其他内容，则退出循环。

然后对于每个索引，检查先前索引的组合是否为字符（组合 < 27）。如果为真，则将索引-2之前的字符串的结果添加到其中。

将每个增量子字符串的结果存储在字典中。

结果：

result_dict 包含以下值：

{'12': 2, '12531': 3, '1': 1, '125312': 6, '125': 3, '1253': 3}

所以result_dict[st]给出了所需的答案

使用列表是一个更好的想法

def decode_string(st):
    result_list = [1]
    for i in xrange(2,len(st)+1):
        if int(st[i-1]) == 0:
            if int(st[i-2]) not in [1,2]:
                return "Not possible to decode"

            result_list.append(0)

        else:
            result_list.append(result_list[i-2])

        if int(st[i-2:i]) < 27 and st[i-2] != '0':
            if i>2:
                result_list[i-1] = result_list[i-1] + result_list[i-3]
            else:
                result_list[i-1] = result_list[i-1] + 1
    print result_list
    return result_list[-1]

print decode_string("125312")