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.

/*
For it wants us to return all possible letter combinations, it is a problem of search. We can use DFS or BFS to solve it.
*/

//DFS: time:O(2^n), space:O(1)

public class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return ans;
        }
        String[] map = {"", "", "abc", "def", "ghi", "jkl", 
                        "mno", "pqrs", "tuv", "wxyz"};
        helper(map, digits, ans, "");
        return ans;
    }
    public void helper(String[] map, String digits, 
                       List<String> ans, String str) {
        if (str.length() == digits.length()) {
            ans.add(str);
            return;
        }
        int num = digits.charAt(str.length()) - '0';
        for (char ch : map[num].toCharArray()) {
            helper(map, digits, ans, str + ch);
        }
    }
}


//BFS: time:O(2^n), space:O(2^n)

public class Solution {
    public List<String> letterCombinations(String digits) {
        List<String> ans = new ArrayList<>();
        if (digits == null || digits.length() == 0) {
            return ans;
        }
        String[] map = {"", "", "abc", "def", "ghi", 
                        "jkl", "mno", "pqrs", "tuv", "wxyz"};
        Queue<String> queue = new LinkedList<>();
        queue.add("");
        for (int i = 0; i < digits.length(); i++) {
            int num = digits.charAt(i) - '0';
            while (queue.peek().length() == i) {
                String str = queue.poll();
                for (char ch : map[num].toCharArray()) {
                    queue.offer(str + ch);
                }
            }
        }
        while (!queue.isEmpty()) {
            ans.add(queue.poll());
        }
        return ans;
    }

}