题目描述
链接
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
image.png
思路
- 回溯法
- 首先将数字和对应的字母存储在二维数组里。
- 回溯过程维护一个过程集字符串StringBuilder，表示已有字母排列，初始为空。每取数字字符串的一位数字，从二维数组中取对应一行字母，并将其中一个字母插入到已有字母排列中，然后继续处理数字字符串的后一位数字，直到处理完所有数字，即得到一个完整的字母排列。再进行回退操作，遍历其余的字母排列。
java 代码如下：
class Solution {
char[][] arr = {{},{},{'a','b','c'},{'d','e','f'},{'g','h','i'},{'j','k','l'},
{'m','n','o'},{'p','q','r','s'},{'t','u','v'},{'w','x','y','z'}};
List<String> result = new ArrayList();
StringBuilder way = new StringBuilder();
public List<String> letterCombinations(String digits) {
if(digits.length() == 0){
return result;
}else if(digits.length() == 1){
int i = digits.charAt(0)-'0';
for(int j = 0;j<arr[i].length;j++){
result.add(arr[i][j]+"");
}
}else{
fun(digits,0);
}
return result;
}
public void fun(String digits,int currentNum){
if(currentNum >= digits.length()){
if(currentNum == digits.length()){
result.add(way.toString());
}
return;
}
int i = digits.charAt(currentNum)-'0';
for(int j = 0;j<arr[i].length;j++){
way.append(arr[i][j]+"");
fun(digits,currentNum+1);
way.deleteCharAt(way.length()-1);
}
}
}
遇到的问题
- 二维数组的初始化
- 动态初始化
int [ ][ ] arr=new int [5][3]; // 也可以理解为“5行3例”
- 静态初始化
//静态初始化可用于不规则二维数组的初始化
int [][] arr=new int[][]{{4,5,6,8},{2,3},{1,6,9}};
- java 中 String、StringBuilder、StringBuffer
2.1 区别
- String一般作为简单字符串类型,StringBuffer字符串缓冲区，StringBuider：字符串缓存区；
- 运行速度(执行速度)，在这方面运行速度快慢为：StringBuilder > StringBuffer > String ;String最慢的原因是：String为字符串的常量而StringBuilder和StringBuffer是字符串的变量，String一旦创建之后是不可更改的，Java中对String对象进行的操作实际上是一个不断创建新的对象并且将旧的对象回收的一个过程，所以执行速度很慢；而StringBuilder和StringBuffer是变量是可以更改的
- 在线程安全上，StringBuilder是线程不安全的，而StringBuffer是线程安全的。StringBuffer中很多方法可以带有synchronized关键字，所以可以保证线程是安全的，但StringBuilder的方法则没有该关键字，所以不能保证线程安全
- 适用场景：
String：适用于少量的字符串操作的情况；
StringBuilder：适用于单线程下在字符缓冲区进行大量操作的情况；StringBuffer：适用多线程下在字符缓冲区进行大量操作的情况
2.2 String 的方法总结
- 返回指定索引处的 char 值
char charAt(int index);
- 返回此字符串的长度
int length();
- 将此字符串转换为一个新的字符数组
char[] toCharArray();
2.3 StringBuilder的方法总结
- length()方法用于返回此序列的长度。
- append()追加字符串
- delete()方法用于删除此序列给定范围内的字符。
- 去掉最后一个字符
StringBuilder s=new StringBuilder();
s.deleteCharAt(s.length()-1);
