微软面试题： LeetCode 91. 解码方法出现次数：3

题目描述：

一条包含字母 A-Z 的消息通过以下方式进行了编码：

'A' -> 1
'B' -> 2
...
'Z' -> 26
给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1：

输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

示例 2：

输入：s = "0"
输出：0

分析：

　　因为 s[0:i] 的解码方案可以由 s[0:i-1] 的解码方案和 s[i] 的值推导得到

所以可以使用动态规划算法解决。下面具体分析：

　　给定数字字符串 "1226" ，去掉最后一位得到子串 "122" ，"122" 可解码

为 1,2,2 12,2 1,22 三种，"1226"的解码方案是将字符 '6' 加到 "122"的所有解码方案中

对1，2，2 生成"1226"的解码序列有两种选择，'6' 单独作一位加在后面 1，2，2，6

或 '6' 和最后一位2拼接成 1，2，26 。由 "122"的解码方案生成 "1226"的解码方案有

1，2，2，6 　　1，2，26　　12，2，6　　12，26 　　1，22，6

即可以根据 s[0:i-1] 的解码方案和 s[i] 的值推出 s[0:i] 的解码方案。需要特别考虑 s[i-1] 和 s[i] 为 '0' 的情况。

1. 定义状态 dp[i] ：s[0 : i] 的所有解码， np[i] s[0 : i] 的所有解码中，最后一个编码是1位的解码，如对 "122"

的解码 1,2,2 12,2 1,22 dp[2] = 3 ，np[2] = 2 。

状态转移和状态空间压缩见下面代码和注释：

 1 class Solution {

 2 public:

 3     int numDecodings(string s)

 4     {

 5         int dp ;

 6         int np ;

 7         //base case

 8         if(s[0] == '0'){

 9              dp = 0;

10              np = 0;

11         }

12         else

13         {

14             dp = 1;

15             np = 1;

16         }

17         //state move

18         for(int i = 1;i < s.size();++i)

19         {

20             if(s[i-1] == '0')//s[0:i-1] 有效的结尾只可能是 10，20，

21             {

22                 if(s[i] == '0') //‘0’ 既不能拼接在 10，20 后面，也 单独作一位

23                 {

24                     dp = 0;

25                     np = 0;

26                 }

27                 //非‘0’ 可以单独作一位

28                 else

29                 {

30                    if(dp > 0)//单独作一位跟在 ‘10’ ‘20’ 后面

31                    {

32                        // dp = dp;

33                         np = dp;

34                    }

35                    else//s[0:i-1] 没有合法的解码方法

36                    {

37                        dp = 0;

38                        np = 0;

39                    }

40                 }

41             }

42             else if(s[i] == '0') // s[i-1] ！= '0' ，s[i] == '0'

43          // s[i] == '0' 只能在 s[i-1]是 1或2 的时候与之拼接成‘10’或’20‘，不能在其他情况下拼接，也不能单独作一位

44             {

45                 if(s[i-1] == '1' || s[i-1] == '2') //s[i-1]是 1或2 的时候与之拼接成‘10’或’20‘

46                 {

47                     dp = np;

48                     np = 0;

49                 }

50                 else

51                 {

52                     dp = 0;

53                     np = 0;

54                 }

55             }

56             //s[i]和s[0:i-1]的所有解码序列 即可拼接又可单独作一位

57             else if(s[i-1] == '1' || (s[i-1] == '2' && s[i] >= '1' && s[i] <= '6'))

58             {

59                int temp = dp;

60                 dp = dp + np;

61                 np = np + (temp - np);

62             }

63             // s[i-1] 不是 0，1，2  s[i] 不是0，s[i]只能单独作一位

64             else

65             {//dp 不变 所有的s[0:i-1]的 2位结尾的解码，全部都变成 1位结尾的解码，1位结尾的解码依然是一位结尾的解码

66               //  dp = dp;

67                 np = dp;

68             }

69         }

70         return dp;

71     }

72 };

巴特西

微软面试题： LeetCode 91. 解码方法出现次数：3

最新文章

热门文章

巴特西

微软面试题： LeetCode 91. 解码方法 出现次数：3

最新文章

热门文章

微软面试题： LeetCode 91. 解码方法出现次数：3