题目

代码

class Solution {
     //设置全局列表存储最后的结果
    List<String> result = new ArrayList<>();
    //初始对应所有的数字，为了直接对应2-9，新增了两个无效的字符串""
    String[] numString = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    //每次迭代获取一个字符串，所以会设计大量的字符串拼接，所以这里选择更为高效的 StringBuilder
    StringBuilder sb = new StringBuilder();
    public List<String> letterCombinations(String digits) {
        if(digits == null || digits.length() == 0 ) {
            return result;
        }
        backtracking(digits,0);
        return result;
    }
    public void backtracking(String digits,int num) {
        //遍历全部一次记录一次得到的字符串
        if(num == digits.length() ) {
            result.add(sb.toString() );
            return ;
        }
        //str 表示当前num对应的字符串
        String str = numString[ digits.charAt(num) - '0'];
        for(int i = 0; i < str.length(); i++ ) {
            sb.append(str.charAt(i) );
            //注意是num+1,不然会java.lang.StackOverflowError
            backtracking(digits,num + 1);
            //剔除末尾的继续尝试
            sb.deleteCharAt(sb.length() -1 );
        }
    }
}