Google 面试题 | 解码方法2

1,226 阅读6分钟

专栏 | 九章算法
网址 | www.jiuzhang.com

题目描述

一个包含A到Z的消息通过如下方式加密:
'A' -> 1
'B' -> 2
...
'Z' → 26

除了上述规则外,加密字符串还可能包含字符'',可以将其视为一个1到9之间的数字字符。给定一个包含数字字符和''的加密信息,问有几种解码方式。由于答案可能很大,只需返回答案对10^9+7取模后的结果即可。

样例1:
输入: "*"
输出: 9
说明: 该加密信息可解码为这些字符串:"A", "B", "C", "D", "E", "F", "G", "H", "I"。

样例2:
输入: "1"
输出: 18
说明: "1
"可以表示"11"、"12"、……、"19",每种表示都既可以解码成单个字符,也可以解码成两个字符,答案为9+9=18。

解题思路分析

这道题算是 解码方法1 的follow up,区别在于加入了一个通配符*可以用划分型动态规划解决,因为对于一个加密字符串,将其最后一位单独划分出来,该位的解码方案数与前面剩下的字符串的解码方案数互不影响,相互独立,将两者相乘即可得到这种情况的方案总数,再考虑将最后两位单独划分出来解码为一个字符的的情况,用同样的方法得到方案数,将两者相加即可得到原问题的总方案数。

解码方法 中,考虑当前位是单独解码成一个字符还是与前一位一起解码成一个字符,在这题中,也是进行相同的考虑,只不过面对的情况多一点而已。

状态表示以及初始化:设加密字符串为s,s的第i位为s[i-1],f[i]表示s的前i个字符的解码方式的数量,f[0]=1

状态转移:

s[i-1]单独解码成一个字符:

s[i-1]为数字字符:若s[i-1]=='0',则s[i-1]不能单独解码为一个字符,对f[i]的贡献为0;若s[i-1]!='0',则s[i-1]可以解码为一个字符,同时,前i-1位有f[i-1]种解码方式,这种情况对f[i]的贡献为f[i-1]。

s[i-1]=='':s[i-1]可以解码成一个字符而且有9种可能,对于每一种可能,前i-1位都有f[i-1]中解码方式,故这种情况共有9f[i-1]中解码方式。

s[i-2]和s[i-1]一起解码成一个字符:

s[i-2]和s[i-1]都是数字字符:若组成的数字不在10到26之间,则s[i-2]和s[i-1]不能一起解码成一个字符,对f[i]的贡献为0;否则,s[i-2]和s[i-1]可以一起解码成一个字符,对f[i]的贡献为f[i-2]。

若s[i-1]=='*',s[i-2]为数字字符:这种情况下,只有"1"和"2"可以解码成一个字符,所以若s[i-2]不为'1'或者'2',那么s[i-2]和s[i-1]不能一起解码成一个字符,对答案的贡献为0;若s[i-2]=='1',则"1"可以表示成"11"、"12"、……、"19",解码为"K"到"S",共9种可能,对于每一种可能,前i-2位都有f[i-2]种解码方式,贡献为9f[i-2];若s[i-2]=='2',则"2"可以表示成"21"、"22"、"23"、"24"、"25"、"26"可以解码成一个字符,共6种可能,同样的,其贡献为6f[i-2]。

若s[i-2]=='*',s[i-1]为数字字符:同样考虑这两位形成的数字可能的范围(10~26)。若s[i-1]在'0'到'6'之间,那么s[i-2]可以取'1'或'2'两种可能,对f[i]的贡献为2*f[i-2];若s[i-1]在'7'到’9‘之间,那么s[i-1]只能取'1',否则是无法将两个字符一起解码成一个字符的,对f[i]的贡献为f[i-2]。

若s[i-2]和s[i-1]均为'*':"*",由于''可以表示为1到9,而要解码成一个字符要求数字范围在10~26,故解码成一个字符的方法有15种,即11~19以及21~26,对f[i]的贡献为15*f[i-2]。

所有涉及的计算都应该对10^9+7取模,并且注意到有乘法可能会使中间结果溢出32位整数,计算时应进行类型转换。最后答案为f[n],n为加密字符串的长度。算法的时间复杂度为O(n),空间复杂度为O(n)。

参考程序

www.jiuzhang.com/solution/de…

面试官角度分析

这道题是划分型动态规划的题目,当加入'*'后题目变得稍微复杂,但基本思想仍是一样的,仔细分析可能的各种情况即可。

题目难点在于状态转移时情况繁多,需要cover所有可能出现的case,给出正确的解法可以hire。

lintcode相关问题

www.lintcode.com/zh-cn/probl…


推荐阅读:



欢迎关注我的微信公众号:九章算法(ninechapter)。
精英程序员交流社区,定期发布面试题、面试技巧、求职信息等

九章算法,IT教育领域的深耕者
九章算法,IT教育领域的深耕者