17. Letter Combinations of a Phone Number

給一個電話按鈕如下圖，每個數字都對印若干英文字，傳入數字組digits，回傳所有可能的英文字母組合。

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

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

這題就是列出n!的結果，主要是難在根據傳入的數字組，使用動態迴圈來跑出所有組合。

嘗試使用遞迴來處理，遞迴接收digits和index，如果digits不是最後一組則再次呼叫遞迴，直到全部的數字組都完成。

寫成程式碼如下

         String[][] phone = new String[][] {   
		{}, 
		{}, 
		{ "a", "b", "c" }, 
		{ "d", "e", "f" }, 
		{ "g", "h", "i" },
		{ "j", "k", "l" }, 
		{ "m", "n", "o" }, 
		{ "p", "q", "r", "s" }, 
		{ "t", "u", "v" }, 
		{ "w", "x", "y", "z" } 
        };

	public List<String> letterCombinations(String digits) {

		List<String> ans = new ArrayList<>();
		if ("".equals(digits)) {
			return ans;
		}

		// 傳入初始index以及數組digits
		appendString(0, digits.toCharArray(), ans, "");

		return ans;
	}

	public void appendString(int index, char[] charArray, List<String> ans, String now) {

		// 逐筆跑本次數字所擁有的英文字
		for (String key : phone[charArray[index] - '0']) {
			// 確認是否是最後一組數字，若還有則往後呼叫
			if (index + 1 < charArray.length) {
				int tmp = index + 1;
				// 將目前已組合的字串now + key傳入，供下一組串接使用
				appendString(tmp, charArray, ans, now + key);
			} else {
				// 已經無下一組，將串完的字串放入List
				ans.add(now + key);
			}
		}

	}