一条包含字母 A-Z 的消息通过以下方式进行了编码:
'A' -> 1 'B' -> 2 ... 'Z' -> 26
给定一个只包含数字的非空字符串,请计算解码方法的总数。
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); System.out.println(DecodeCount(s)); } public static int DecodeCount(String strs){ int[] s = new int[strs.length()]; for(int i = 0; i < strs.length(); i++){ char c = strs.charAt(i); s[i] = c - '0'; } int[] dp = new int[strs.length()]; if(s[0] == 0) return 0; dp[0] = 1; if (s[0] * 10 + s[1] <= 26 && s[0] * 10 + s[1] > 0){ dp[1] = s[1] == 0 ? 1 : 2; }else{ if(s[1] == 0) return 0; dp[1] = 1; } for(int i = 2; i < s.length; i++){ if(s[i - 1] * 10 + s[i] <= 26 && s[i - 1] * 10 + s[i] > 0){ dp[i] = s[i] == 0 ? dp[i - 2] : dp[i - 2] + dp[i - 1]; }else{ if(s[i] == 0) return 0; dp[i] = dp[i - 1]; } } return dp[strs.length() - 1]; } }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); char[] str = br.readLine().toCharArray(); System.out.println(dfs(str, 0)); } private static int dfs(char[] str, int depth) { if(depth >= str.length){ // 字符串末尾匹配完了,增加一种翻译方案 return 1; }else{ if(str[depth] == '0'){ // 本层单独面对一个0,之前的翻译有误,这个0应该与前一个字符结合 return 0; } // 本层字符单独成为一种翻译 int ways = dfs(str, depth + 1); if(str[depth] == '1' && depth < str.length - 1){ // str[depth]与str[depth + 1]翻译成j~s ways += dfs(str, depth + 2); }else if(str[depth] == '2' && depth < str.length - 1 && (str[depth + 1] >= '0' && str[depth + 1] <= '6')){ // str[depth]与str[depth + 1]翻译成t~z ways += dfs(str, depth + 2); } return ways; } } }递归逻辑是最朴素直观的思考过程,有了递归逻辑,就可以很轻松地改出动态规划版本。
import java.util.Scanner; //47 public class Main{ //递归版 private static char[] ch = new char[27]; private static int res; public static void main(String[] args) { Scanner sc = new Scanner(System.in); char[] arr = sc.next().toCharArray(); ch[1] = 'A'; for(int i=2;i<27;i++){ ch[i]=(char) (ch[i-1]+1); } count(arr, 0, arr.length-1); System.out.println(res); } static void count(char[] arr,int s,int e){ if(s>=e){ res++; return; } if(s+1<=e){ if(Integer.parseInt(arr[s]+""+arr[s+1])<=26){ count(arr,s+2,e); } } count(arr, s+1, e); } }