Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example:

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

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

LeetCode: Letter Combinations of a Phone Number 解题报告 - Yu's Garden - 博客园www.cnblogs.com

和permutation和factor combanition一个套路，时间复杂度 o(n4^n), string转换的时候，o(n), 每个数字对应最多4个字母，总共的组合就是4的n次方

string builder deletecharat 最后一个字母是o(1),一般都是o(n)

o(n*4^n) ---> o(4^n) , space o(n) n层栈

class Solution {
    public List<String> letterCombinations(String digits) {
        
        
        char[][] charArr = 
        {
            {},
            {},
            {'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> res = new ArrayList<>();
        if(digits == null || digits.length() == 0)
            return res;
        
        StringBuilder cur = new StringBuilder();
        backtracking(res,cur,0,digits,charArr);
        
        return res;
    }
    
    public void backtracking(List<String> res, StringBuilder cur, int l, String digits,char[][] charArr){
        if(l == digits.length()){
            res.add(cur.toString());
            return;
        }
        
        for(char c : charArr[digits.charAt(l)-'0']){
            cur.append(c);
            
            backtracking(res,cur,l+1,digits,charArr);
            cur = cur.deleteCharAt(cur.length()-1);//o(n)
        }
    }
}