#17 Letter Combinations of a Phone Number

電話上的數字按鍵都會有對應的英文字母：

2 = "abc", 3="def", 4 ="ghi"...

輸入一串數字，找出所有可能的字母組合。

想法：不管input有幾個數字，我可以把題目想成一個數字對應的字母們 和 一個List<String>的排列

實作上用String array來存數字和字母的對應關係，

String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

然後宣告一個List<String> str來儲存所有要和某數字的字母們組合的字串。

初始化str為所有最後一個數字對應的字母。例如：87，則將str放入"p","q","r","s"。

for每個digits中的數字，（從倒數第二個數字開始往前跑）

    將此數字對應的字母們接到str中的每個string

完整程式碼：

public class Solution {
    public List<String> letterCombinations(String digits) {
        //String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        //No matter how many digits there are, I can regard it as permutation of 1 digit's letters and 1 List<String>

        //create a List<String> str to hold the strings that are going to combine with letters corresponding to a digit
        //first, put corresponding letters in the last digit in digits into str
        //for each digit in digits(starts from charAt(n-2))
        // concate each mapped letters to each string in str

        //return str

        String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        List<String> ans = new ArrayList<>();

        if(digits.length()==0) 
            return ans;

        char c = digits.charAt(digits.length()-1);
        int i = Character.getNumericValue(c);
        for(int j=0; j<mapping[i].length(); j++)
            ans.add(j,""+mapping[i].charAt(j));

        for(int j=digits.length()-2; j>=0; j--){//for each digit in digits
            c = digits.charAt(j);
            i = Character.getNumericValue(c);
            List<String> str= new ArrayList<>();
            int count = 0;
            for(int k=0; k<mapping[i].length(); k++){//for each letter corresponding to i
                char cOfDigit = mapping[i].charAt(k);
                for(int m=0; m<ans.size(); m++){//for each string in ans
                    String s = cOfDigit+ans.get(m);
                    str.add(count,s);
                    count++;
                }
            }
            ans = str;
        }

        return ans;
    }
}