🔓 165.解密数字
现有一串神秘的密文 ciphertext，经调查，密文的特点和规则如下：
- 密文由非负整数组成
- 数字 0-25 分别对应字母 a-z
请根据上述规则将密文 ciphertext 解密为字母，并返回共有多少种解密结果。
示例
1
2
3
| 输入: ciphertext = 216612
输出: 6
解释: 216612 解密后有 6 种不同的形式，分别是 "cbggbc"，"vggbc"，"vggm"，"cbggm"，"cqggbc" 和 "cqggm"
|
思路
基本思想
按照示例给出的情况，可以理解为给出一个ciphertext，将其划分成不同的数字，只要当前这种划分方案符合划分中的每个数字都大于等于0且小于26，并且没有00,07这种类似的情况出现即可。第一想法就是将当前数字转换成字符串，然后使用字符串的划分方法
字符串的划分可以使用回溯法，这样就可以找到字符串的所有划分方案，在回溯进行向下递归时，增加一些判断条件就可以对划分方案进行筛选，基本的字符串划分方案是：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
| //其中path是记录当前划分方案的，list是记录所有的分割方案的
public void backtrack(String str, int index) {
if (index == str.length()) {
list.add(new ArrayList<>(path));
return;
}
for (int i = index; i < str.length(); ++i) {
String subStr = str.substring(index, i + 1);
path.add(subStr);
//在回溯向下递归时，可以增加一些筛选条件，从而使得划分方案变少
backtrack(str, i + 1, path, list);
path.remove(subStr);
}
}
|
有了这种字符串的通用划分方案，在这个基础上进行筛选，只有每个数字都大于等于0且小于26，并且没有00,07这种类似的情况出现的方案才满足要求，所以每次划分之前需要先进行判断
执行流程
- 进行字符串的划分，划分的过程中需要进行判断
- 每个数字都大于等于0且小于26，并且没有00,07这种类似的情况出现才可以进行回溯的向下递归
- 形成一种完整的方案时不需要保存划分方案，只需要记录出现了多少种方案即可
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
//把密文拆分，拆分成不同的符合要求的数，然后再返回结果
//考的是一道字符串拆分的题目
int res=0;
public int crackNumber(int ciphertext) {
String str=""+ciphertext;
if(str.length()==0)
return 0;
help(str,0);
return res;
}
//回溯法统计所有合法的分割结果，有多少分割结果就能解密出多少种可能
//分割字符串的方法需要记住
private void help(String str,int index){
if(index==str.length()){
res++;
return;
}
for(int i=index;i<str.length();++i){
String substr=str.substring(index,i+1);
int num=Integer.valueOf(substr);
//当前分割结果还在26以内并且不能出现07,00这种情况
if(num==0&&substr.length()==1||num<26&&substr.charAt(0)!='0'){
help(str,i+1);
}else{//超过直接结束
break;
}
}
}
}
|
总结
主要是学会将问题转换成字符串划分的问题，然后在通用的字符串划分模版的基础上增加筛选条件即可得到所有合法的划分结果，从而返回答案