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.

Solution:

public class Solution {
    char[][] map={" ".toCharArray(), "".toCharArray(), 
    "abc".toCharArray(), "def".toCharArray(), "ghi".toCharArray(), 
    "jkl".toCharArray(), "mno".toCharArray(), "pqrs".toCharArray(), 
    "tuv".toCharArray(), "wxyz".toCharArray()};
    int length=0;
    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<String>();
        length=digits.length();
        if(length==0)return res;
        char[] tmp = new char[length];
        char[] newdigits = digits.toCharArray();
        getLetterCom(res,0,newdigits,tmp);
        return res;
    }
    private void getLetterCom(List<String> res,int index,char[] digits,char[] tmp){
        if(index>=length){
            String letters = new String(tmp);
            res.add(letters);
            return;
        }
        int digit=digits[index]-'0';
        for(int i=0;i<map[digit].length;i++){
            tmp[index]=map[digit][i];
            getLetterCom(res,index+1,digits,tmp);
        }
    }
}

C语言源代码（用时1ms）：

void getLetterCom(char** res,char* digits,char* tmp,int index,char map[10][5],int *top){
    int i,digit=digits[index]-'0';
	char* letters;
    if(digits[index]==0){
        letters=(char*)malloc(sizeof(char)*index);
        tmp[index]=0;
		strcpy(letters,tmp);
        res[*top]=letters;
		(*top)++;
        return;
    }
    for(i=0;map[digit][i];i++){
        tmp[index]=map[digit][i];
        getLetterCom(res,digits,tmp,index+1,map,top);
    }
}
char** letterCombinations(char* digits, int* returnSize) {
	 char map[10][5]={" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
     char** res,*tmp;
     int num=1,length=0,top=0;
     while(digits[length]){
         if(digits[length]=='0' || digits[length]=='1')continue;
         else if(digits[length]=='7' || digits[length]=='9')num*=4;
         else num*=3;
         length++;
     }
     res=(char**)malloc(sizeof(char*)*num);
     if(length==0){
         *returnSize=0;
         return res;
     }
     tmp=(char*)malloc(sizeof(char)*length);
     getLetterCom(res,digits,tmp,0,map,&top);
     *returnSize=top;
     return res;
}

C++源代码（用时3ms）：

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> res;
        length=digits.size();
        if(length==0)return res;
        char* tmp=(char*)malloc(sizeof(char)*(length+1));
        getLetterCom(res,0,digits,tmp);
        return res;
    }
private:
    char map[10][5]={" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    int top=0,length=0;
    void getLetterCom(vector<string>& res,int index,string digits,char* tmp){
        if(index>=length){
            tmp[index]=0;
            string letters=string(tmp);
            res.push_back(letters);
            return;
        }
        int digit=digits[index]-'0';
        for(int i=0;map[digit][i];i++){
            tmp[index]=map[digit][i];
            getLetterCom(res,index+1,digits,tmp);
        }
    }
};

Python源代码（用时69ms）：

class Solution:
    map=[" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
    length=0;res=[]
    # @param {string} digits
    # @return {string[]}
    def letterCombinations(self, digits):
        self.length=len(digits)
        self.res=[]
        if self.length==0:return self.res;
        tmp=['' for i in range(self.length)]
        self.getLetterCom(0,digits,tmp)
        return self.res
    def getLetterCom(self,index,digits,tmp):
        if index>=self.length:
            letters=''.join(tmp)
            self.res.append(letters)
            return
        digit=ord(digits[index])-ord('0')
        for i in range(len(self.map[digit])):
            tmp[index]=self.map[digit][i]
            self.getLetterCom(index+1,digits,tmp)