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.

思路：使用递归。

public class Solution {
	List<String> result = new ArrayList<String>();
	String[] string = new String[] { " ", "", "abc", "def", "ghi", "jkl", "mno",
			"pqrs", "tuv", "wxyz" };

	public List<String> letterCombinations(String digits) {
		result.add(new String(""));
		if (digits.length() == 0)
			return result;
		letterOfCombinations(digits);
		return result;
	}

	public void letterOfCombinations(String digits) {
		int tmp = (int) (digits.charAt(0) - '0');
		int len = result.size();
		int i, j;
		for (i = 0; i < string[tmp].length() - 1; i++) {
			for (j = 0; j < len; j++) {
				result.add(new String(result.get(j)));
			}
		}
		for (i = 0; i < result.size(); i++) {
			j = i / len;
			String str = result.get(i) + string[tmp].charAt(j);
			result.set(i, str);
		}
		if (digits.length() == 1) return;
		letterOfCombinations(digits.substring(1));
	}
}

LeetCode 18 Letter Combinations of a Phone Number