[LeetCode] 17. Letter Combinatio

</br>

---

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.

---

</br>

Solution

Whenever a digit is touched, this digit may represent three or four characters. And when the next digit is touched, we have to iterate every existing string, and then appending the next three or four different characters to the end of those.

This process can be hard to proceed if there is no appropriate method. However, instead of trying to achieve the goal in one pass, we can update the answer every time a digit is touched. When the next digit is touched, we pick out all strings currently in the ArrayList[answer] and individually add new characters behind them. In this way, we can lay out all possible combinations.

In order to make sure the algorithm enter the for loop for the first time, we should initialize the ArrayList[answer] to "", so that the ans.size() is above zero.

One more thing, when we set the ArrayList[answer] to "", we have to take care of the empty situation. If the input is empty [], we should have a if sentence to return empty ArrayList.

The code is shown as below.

Java

public class Solution {
    public List<String> letterCombinations(String digits) {
        
        String[] alphabet = {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        ArrayList ans = new ArrayList();
        ArrayList empty = new ArrayList();
        
        //Initialize ans, otherwise we can start the very first for loop.
        ans.add("");
        
        
        if (digits.length() == 0)
            return empty;
            
        for (int i = 0; i < digits.length(); i++){
            ArrayList subans = new ArrayList();
            String chars = alphabet[digits.charAt(i) - '0'];
            
            for (int c = 0; c < chars.length();c++)
                for (int j = 0; j < ans.size();j++)
                    subans.add(ans.get(j) + String.valueOf(chars.charAt(c)));
                
            ans = subans;
        }
        return ans;
    }
}

</br>