解码方法

1.题目

2.思路

1）我们定义一个数组dp，其中dp[i]表示字符串s的前i个字符的解码方法总数。初始化时，dp[0]为1，因为空字符串有一种解码方式。dp[1]的值取决于第一个字符是否是'0'，如果不是'0'，则有一种解码方式，否则没有解码方式。

2）从第三个字符开始遍历字符串s（即i从2开始）。对于每个字符，我们考虑两种可能的解码方式：

1. 单独解码最后一个字符：如果当前字符不是'0'，则它可以单独解码成一个字母。因此，我们可以将dp[i]增加dp[i-1]，因为这意味着我们保持之前的解码方式不变，并在末尾添加一个新的解码字符。

2. 组合解码最后两个字符：我们检查最后两个字符组成的数字是否在10到26之间。如果是，这两个字符可以组合起来解码成一个字母。在这种情况下，我们可以将dp[i]增加dp[i-2]，因为这意味着我们不考虑最后一个字符，而是将最后两个字符作为一个整体进行解码，并加上之前的解码方式数。

在遍历完整个字符串后，dp[n]（其中n是字符串s的长度）将包含整个字符串的解码方法总数。

3.代码

import java.util.Scanner;public class jiema {//定义方法numDecodings,接收一个字符串s作为参数，返回解码方法的总数public int numDecodings(String s) {if(s==null || s.length()==0 || s.charAt(0)=='0') {return 0;}//定义dp数组，dp[i]表示s的前i个字符的解码方法总数int n=s.length();int[] dp = new int[n+1];//空字符串有一种解码方式dp[0]=1;//第一个字符如果不是‘0’，则有一种解码方式，否则没有dp[1]=s.charAt(0)!='0'?1:0;//从第二个字符开始遍历字符串sfor(int i=2;i<=n;i++) {//情况1：单独解码最后一个字符//如果当前字符不是'0'，则可以单独解码成一个字母if(s.charAt(i-1)!='0') {dp[i]+=dp[i-1];}//情况2：组合解码最后两个字符//取最后两个字符组成的数字int twoDigit = Integer.parseInt(s.substring(i-2,i));//如果这个数字在10-26之间，则可以组合解码成一个字母if(twoDigit >= 10&&twoDigit <=26) {dp[i]+=dp[i-2];}}return dp[n];}public static void main(String[] args) {//创建对象jiema solution=new jiema();Scanner scanner=new Scanner(System.in);String s=scanner.nextLine();scanner.close();//调用numDecodings方法int result = solution.numDecodings(s);System.out.println(result);}
}

4.知识

1）s.charAt(0)

在Java中，s.charAt(0) 是一个方法调用，用于获取字符串 s 中位于索引 0 的字符。在Java中，字符串是字符的序列，并且索引是从 0 开始的。因此，s.charAt(0) 会返回字符串 s 的第一个字符。

例如，如果有一个字符串 s = "hello"，那么 s.charAt(0) 将返回字符 'h'。

这里是 s.charAt(0) 的一些要点：

• 如果字符串 s 是空的（即 s.length() == 0），那么调用 s.charAt(0) 会抛出一个 StringIndexOutOfBoundsException，因为索引 0 不存在。
• 如果 s 是 null，那么调用 s.charAt(0) 将会抛出一个 NullPointerException，因为你不能在 null 对象上调用方法。

因此，在调用 s.charAt(0) 之前，通常最好检查字符串 s 是否为空或 null，以避免这些异常。

2）int twoDigit = Integer.parseInt(s.substring(i-2,i));

Integer.parseInt() 方法用于将字符串参数作为有符号的十进制整数进行解析。如果字符串参数以有效的十进制数字序列开始，则该方法将返回该序列表示的整数。

在代码 int twoDigit = Integer.parseInt(s.substring(i-2, i)); 中，s.substring(i-2, i) 创建了一个从字符串 s 的 i-2 位置开始（包含）到 i 位置结束（不包含）的子字符串。这个子字符串包含了 s 的最后两个字符。

3）   Scanner scanner=new Scanner(System.in);
        String s=scanner.nextLine();
        scanner.close();

从键盘获取字符串的代码，导入包import java.util.Scanner;