题目描述

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.

• 思路
  求给定数字串对应字母的所有组合情况。
  遍历数字串，每次循环当前数字的所有字母并组合，然后递归找下一个。

import java.util.*;
public class Solution {
    public ArrayList<String> letterCombinations(String digits) {
        ArrayList<String> list = new ArrayList<String>();
        if(digits == null)
            return list;
        
        String[] str = {
            "",
            "",
            "abc",
            "def",
            "ghi",
            "jkl",
            "mno",
            "pqrs",
            "tuv",
            "wxyz"
        };
        
        combinations(digits, 0, "", str, list);
        return list;
    }
    
    public void combinations(String dig, int pos, String s, 
                             String[] str, ArrayList<String> list){
        if(pos == dig.length()){
            list.add(s);
            return ;
        }
        
        String string = str[dig.charAt(pos) - '0']; //取得数字对应的字母集
        for(int i=0; i<string.length(); i++){
            combinations(dig, pos+1, s + string.charAt(i), str, list);
        }
    }
}