91. 解码方法 ——【Leetcode每日刷题】

妖狐艹你老母 2024-03-26 19:52 31阅读 0赞

### 91. 解码方法 ###

一条包含字母 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  
> 解释：它可以解码为 “AB”（1 2）或者 “L”（12）。

##### 示例 2： #####

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

##### 示例 3： #####

> 输入：s = “06”  
> 输出：0  
> 解释：“06” 无法映射到 “F” ，因为存在前导零（“6” 和 “06” 并不等价）。

##### 提示： #####

*  1 <= s.length <= 100
 *  s 只包含数字，并且可能包含前导零。

#### 思路：(动态规划) ####

这道题不要往复杂了想，其实一共就是两种情况，一次解码一个字符和一次解码两个字符，dp\[i\] 就等于这两种情况之和。

dp数组的含义，dp\[i\] 为前 i 个子字符串 (即从 0 ~ i-1) 一共有多少种编码方式。

**递推公式为：**  
 d p \[ i \] = d p \[ i − 1 \] + d p \[ i − 2 \] dp\[i\] = dp\[i - 1\] + dp\[i - 2\] dp\[i\]=dp\[i−1\]\+dp\[i−2\]

特别需要注意的是：

1.  如果 s\[i\] = 0 ，不能单独解码，只能和前一个组合解码，前一个 s\[i-1\] 必须是 1 或者 2，否则超出范围无法解码。
    
     *  如果可以前一个字符s\[i-1\]组合解码，则s\[i-1\]就不能和s\[i-2\]在组合了，此时：dp\[i\] = dp\[i -2\]；
     *  如果不能组合解码，则该字符串无法解码。
2.  如果 s\[i\] 不为0，则肯定可以单独解码，能否组合解码，还要判断组合码是否超出边界，或者无法映射。
    
     *  如果 s\[i\] 可以组合解码则: dp\[i\] = dp\[i - 1\] + dp\[i - 2\] ;
     *  不能组合解码则： dp\[i\] = dp\[i - 1\] 。

#### 代码：(Java) ####

public class DecodingWays {
        
    
    	public static void main(String[] args) {
        
    		// TODO Auto-generated method stub
    		String s = "226";
    		System.out.println(numDecodings(s));
    	}
    	public static int numDecodings(String s) {
        
    		int n = s.length();
    		if(s.charAt(0) == '0')
    			return 0;
    		
    		int []dp = new int[n + 1];
    		
    		dp[0] = dp[1] = 1;
    
    		
    		for(int i = 1; i < n; i++) {
        
    			if(s.charAt(i) == '0' && (s.charAt(i - 1) == '1' || s.charAt(i - 1) == '2')) {
        
    				dp[i + 1] = dp[i - 1];
    			}else if(s.charAt(i) == '0') {
        
    				return 0;
    			}else if(Integer.valueOf(s.substring(i - 1,i + 1)) < 27 && Integer.valueOf(s.substring(i - 1,i + 1)) > 10) {
        
    				dp[i + 1] = dp[i] + dp[i - 1];
    			}else {
        
    				dp[i + 1] = dp[i];
    			}
    		}
    		
    		return dp[n];
        }
    }

##### 运行结果： #####

![在这里插入图片描述][11ed0ac4bde649f1bd9b11d4ffd3edc6.png]

##### 复杂度分析 #####

*  时间复杂度：O(n)，其中 n 是字符串 s 的长度。
 *  空间复杂度：O(n)。使用数组进行状态转移，其中 n 是字符串 s 的长度；

##### 注：仅供学习参考！ #####

题目来源：[力扣。][Link 1]

[11ed0ac4bde649f1bd9b11d4ffd3edc6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/ed1eb71da4e54156a5092db8cbcc83cd.png
[Link 1]: https://leetcode.cn/problems/decode-ways/description/