解码方法

题目描述

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

‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”

要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：

• "AAJF" ，将消息分组为 (1 1 10 6)
• "KJF" ，将消息分组为 (11 10 6)

注意，消息不能分组为 (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。

给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。

题目数据保证答案肯定是一个 32 位 的整数。

示例1

输入： s = “12”
输出： 2

示例2

输入： s = “226”
输出： 3

示例3

输入： s = “06”
输出： 0

题解

依题意得，编码得第一个数字不能为1，则可分为以下部分：

• 当s[0] == '0'，那么直接返回0
• 之后由第二个元素开始遍历
  • 当当前元素为0，那么前一个元素只能为两种情况：
    • 当前一个元素为1或2时，只有一种解法
    • 当前一个元素不为上述两个数，则没有解法
  • 当当前元素为1或2并且前一个元素和当前元素拼接的数字不大于26
    • 有两种解法

最后将遍历结束的值返回即为所求

想法代码

class Solution
{public static void Main(String[] args){string s = "27";Solution solution = new Solution();int ans = solution.NumDecodings(s);Console.WriteLine(ans);}public int NumDecodings(string s){if (s[0] == '0'){return 0;}int pre = 1;int curr = 1;for (int i = 1; i < s.Length; i++){int temp = curr;if (s[i] == '0'){if (s[i - 1] == '1' || s[i - 1] == '2'){curr = pre;}else{return 0;}}else if (s[i - 1] == '1' || s[i - 1] == '2' && (s[i - 1] - '0') * 10 + (s[i] - '0') <= 26){curr = curr + pre;}pre = temp;}return curr;}
}