（每日一练C++）CC131 电话字母的组合

浅浅的花香味﹌ 2023-10-04 17:54 3阅读 0赞

### 描述 ###

给出一个仅包含数字的字符串，给出所有可能的字母组合。

数字到字母的映射方式如下:(就像电话上数字和字母的映射一样)

![19adf3e269766562f15551a7b484d8fc.png][]

Input:Digit string "23"Output:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

注意：虽然上述答案是按字典序排列的，但你的答案可以按任意的顺序给出

### 示例1 ###

输入：

"23"

复制返回值：

["ad","ae","af","bd","be","bf","cd","ce","cf"]

回溯法：http://blog.csdn.net/versencoder/article/details/52071930
    public class Solution {
        List<String> result=new ArrayList<String>();
        public List<String> letterCombinations(String digits) {
            if(digits.length()==0)  return result;
            for(int i=0;i<digits.length();i++){
                if(digits.charAt(i)>'9'||digits.charAt(i)<'2')
                    return result;
            }
            String[] str={"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
            backtracking(str,digits,new StringBuilder(),0,digits.length());
            return result;
        }
        public void backtracking(String[] str,String digits,StringBuilder sb,int start,int k){
            if(k<0)    return ;
            else if(k==0)   {
                result.add(sb.toString());
                //sb=new StringBuilder();
            }
            else{
                for(int i=start;i<digits.length();i++){
                    String s=str[digits.charAt(i)-50];
                    for(int j=0;j<s.length();j++){
                        sb.append(s.charAt(j));
                        backtracking(str,digits,sb,i+1,k-1);
                        sb.deleteCharAt(sb.length()-1);
                    }
                }
            }
        }
    }

[19adf3e269766562f15551a7b484d8fc.png]: https://img-blog.csdnimg.cn/img_convert/19adf3e269766562f15551a7b484d8fc.png