卖萌的弱渣

I am stupid, I am hungry.

Letter Combinations of a Phone Number

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.

Example

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

  • Java
(Letter-Combinations-of-A-Phone-Number.java) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

public class Solution {
    public List<String> letterCombinations(String digits) {
        LinkedList<String> ret = new LinkedList<String>();
        String[] mapping = new String[]{"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        if(digits.length()==0) return ret;
        ret.add("");
        for(int i=0;i<digits.length();i++){
            // x 是在mapping中的索引
            int x = Character.getNumericValue(digits.charAt(i));
            // ret 中peek 长度如果和i相等，则制造下一个digit
            while(ret.peek().length()==i){
                // remove peek element
                String top = ret.remove();
                for(char s : mapping[x].toCharArray())
                    ret.add(top+s);
            }


        }
        return ret;
    }
}
  • Python
(Letter-Combinations-of-a-Phone-Number.py) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution(object):
    tel = {"0":" ", "1": "", "2":"abc", "3":"def", "4":"ghi", "5":"jkl",
     "6":"mno", "7":"pqrs", "8":"tuv", "9":"wxyz"}
    def tel_comb(self,digits,ret,vector):
        if digits:
            codes = self.tel[digits[0]]
            for i in codes:
                self.tel_comb(digits[1:],ret,vector+i)
        else:
            if vector not in ret:
                ret.append(vector[:])

    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        ret = []
        if digits == None or digits == "":
            return ret
        self.tel_comb(digits,ret,"")
        return ret