LeetCode - Letter Combinations of a Phone Number

LetterCombinationsofaPhoneNumber.java

// https://leetcode.com/problems/letter-combinations-of-a-phone-number/

// Solution 1 : Iterative
public List<String> letterCombinations(String digits) {
        String[] maps = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        ArrayList<String> ret = new ArrayList<>();
        if(digits == null || digits.length() == 0){
            return ret;
        }
        ret.add("");
        for(int i=0; i < digits.length(); i++){
            int index = digits.charAt(i) - '0';
            String cur = maps[index];
            ArrayList<String> tempRet = new ArrayList<String>();
            for(int j=0; j < cur.length(); j++){
                char c = cur.charAt(j);
                for(String str : ret){
                    tempRet.add(str + c);
                }
            }
            ret = tempRet;
        }
        return ret;
    }
    
// Solution 2: Recursive (Backtracking)
String[] maps = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List<String> letterCombinations(String digits) {
        ArrayList<String> ret = new ArrayList<>();
        if(digits == null || digits.length() == 0){
            return ret;
        }
        helper(ret, digits, 0, new StringBuilder());
        return ret;
    }
    
    public void helper(ArrayList<String> ret, String digits, int pos, StringBuilder sb){
        if(pos == digits.length()){
            ret.add(sb.toString());
            return;
        }
        int index = digits.charAt(pos) - '0';
        if(index < 2) helper(ret, digits, pos + 1, sb);  // case: "12"
        String curStr = maps[index];
        for(int i=0; i < curStr.length(); i++){
            char curChar = curStr.charAt(i);
            sb.append(curChar);
            helper(ret, digits, pos+1, sb);
            sb.deleteCharAt(sb.length()-1);
        }
    }