算法1

(暴力枚举)

非常暴力

时间复杂度

参考文献

java 代码

class Solution {
    List<String> res = new ArrayList<>();
    char a2[] = new char[]{'a','b','c'};
    char a3[] = new char[]{'d','e','f'};
    char a4[] = new char[]{'g','h','i'};
    char a5[] = new char[]{'j','k','l'};
    char a6[] = new char[]{'m','o','n'};
    char a7[] = new char[]{'p','q','r','s'};
    char a8[] = new char[]{'t','u','v'};
    char a9[] = new char[]{'w','x','y','z'};
    public List<String> letterCombinations(String digits) {
        if(digits.length()==0) return res;
        String str ="";
        dfs(0,digits,str);
        return res;
    }
    public void dfs(int u,String s,String str){
        if(u==s.length()) {res.add(str);return;}
        if(s.charAt(u)=='2')
        {
            for(int i = 0;i<3;i++) dfs(u+1,s,str+a2[i]);
        }
        else if(s.charAt(u)=='3'){
            for(int i = 0;i<3;i++) dfs(u+1,s,str+a3[i]);
        }
         else if(s.charAt(u)=='4'){
            for(int i = 0;i<3;i++) dfs(u+1,s,str+a4[i]);
        }
         else if(s.charAt(u)=='5'){
            for(int i = 0;i<3;i++) dfs(u+1,s,str+a5[i]);
        }
         else if(s.charAt(u)=='6'){
            for(int i = 0;i<3;i++) dfs(u+1,s,str+a6[i]);
        }
         else if(s.charAt(u)=='7'){
            for(int i = 0;i<4;i++) dfs(u+1,s,str+a7[i]);
        }
         else if(s.charAt(u)=='8'){
            for(int i = 0;i<3;i++) dfs(u+1,s,str+a8[i]);
        }
         else if(s.charAt(u)=='9'){
            for(int i = 0;i<4;i++) dfs(u+1,s,str+a9[i]);
        }
    }
}