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. Return the answer in any order.

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 1:

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

Example 2:

Input: digits = ""
Output: []

Example 3:

Input: digits = "2"
Output: ["a","b","c"]

Constraints:

• 0 <= digits.length <= 4

• digits[i] is a digit in the range ['2', '9'].

Solution:

Approach 1: Iterative

class Solution {
    public List<String> letterCombinations(String digits) {
        LinkedList<String> ans = new LinkedList<String>();
		if(digits.isEmpty()) return ans;
		String[] combinations = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
		ans.add("");
		for(int i =0; i<digits.length();i++){
			int x = Character.getNumericValue(digits.charAt(i));
			while(ans.get(0).length()==i){
				String t = ans.remove(0);
				for(char s : combinations[x].toCharArray())
					ans.add(t+s);
			}
		}
		return ans;
    }
}

Approach 2: DFS

class Solution {
    String[] combinations = new String[]{"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    public List<String> letterCombinations(String digits) {
        LinkedList<String> ans = new LinkedList<String>();
        if(digits.isEmpty()) return ans;
        
        dfs(0,new StringBuilder(),digits,ans);
        return ans;
    }
    private void dfs(int i, StringBuilder current, String digits,List<String> ans)
    {
        if(i==digits.length())
        {
            ans.add(current.toString());
            return;
         }
        char curchar = digits.charAt(i);
        for(char neigh:combinations[curchar-'0'].toCharArray())
        {
            current.append(neigh);
            dfs(i+1,current,digits,ans);
            current.deleteCharAt(current.length()-1);
        }
    }
}