Letter Combinations of a Phone Number

Given a digit string, 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.

Input:Digit string "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.

Solution: Recursion
依次读取数字，然后把数字可以代表的字符依次加到当前的所有结果中，然后进入下一次迭代。
假设总共有n个digit，每个digit可以代表k个字符，那么时间复杂度是O(k^n)，就是结果的数量，空间复杂度也是一样。
Run time complexity is O(3^n)

public class Solution {
    public ArrayList letterCombinations(String digits) {
        ArrayList result = new ArrayList();
        if(digits == null || digits.length() == 0) {
            return result;
        }
        
        String[] letter = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        StringBuilder str = new StringBuilder();
        select(digits, letter, digits.length(), result, str);
        return result;
    }
    
    public void select(String digits, String[] letter, int remain, ArrayList result, StringBuilder str) {
        if(remain == 0) {  //说明对digits遍历结束
            result.add(str.toString());
            return;
        }
        
        String s = letter[digits.charAt(0) - '0']; //得到digits[0]对应的string s 
        
        for(int i = 0; i < s.length(); i++) {  //DFS
            str = str.append(s.charAt(i));
            select(digits.substring(1), letter, remain - 1, result, str);
            str.deleteCharAt(str.length() - 1);  //恢复现场
        }
    }
}