leetcode 17. Letter Combinations of a Phone Number 谷歌面试题

Seawolf

1. Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.
   
2. 
   
3. A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.
   
4. 
   
5. 
   
6. Example:
   
7. 
   
8. Input: "23"
   
9. Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
   
10. Note:
    
11. 
    
12. Although the above answer is in lexicographical order, your answer could be in any order you want.

复制代码

1. class Solution {
   
2.     public static List<String> letterCombinations(String digits) {
   
3.         
   
4.         List<String> fi  = new ArrayList<String>();
   
5.         
   
6.         if(digits == null || digits.length() == 0){
   
7.             
   
8.             return fi;
   
9.         }
   
10.         
    
11.         generateString(digits, fi , "");
    
12.         
    
13.         return fi;
    
14.         
    
15.     }
    
16.    
    
17.     public static void generateString(String digits, List<String> fi,String result){
    
18.            
    
19.             if(digits.length() == 0) {
    
20.                    
    
21.                     fi.add(result);
    
22.                    
    
23.                     return;
    
24.             }
    
25.         
    
26.             String head = get_head(digits);
    
27.            
    
28.             String a = "";
    
29.            
    
30.            
    
31.             switch (head) {
    
32.         case "2":
    
33.             a = "abc";
    
34.             break;
    
35.         case "3":
    
36.             a = "def";
    
37.             break;
    
38.         case "4":
    
39.             a = "ghi";
    
40.             break;
    
41.         case "5":
    
42.             a = "jkl";
    
43.             break;
    
44.         case "6":
    
45.             a = "mno";
    
46.             break;
    
47.         case "7":
    
48.             a = "pqrs";
    
49.             break;
    
50.         case "8":
    
51.             a = "tuv";
    
52.             break;
    
53.         case "9":
    
54.             a = "wxyz";
    
55.             break;
    
56.         default:
    
57.             a = "";
    
58.             break;
    
59.         }
    
60.            
    
61.             for(int i = 0; i < a.length(); i++) {
    
62.                    
    
63.                     result = result + a.substring(i,i+1);
    
64.                    
    
65.                     generateString(digits.substring(1,digits.length()),fi,result);
    
66.                    
    
67.                     result = result.substring(0,result.length()-1);
    
68.                    
    
69.             }
    
70.         
    
71.     }
    
72.    
    
73.     public static String get_head(String digits){
    
74.         
    
75.         if(digits == null || digits == ""){
    
76.             
    
77.             return null;
    
78.         }
    
79.         
    
80.         return digits.substring(0,1);
    
81.     }
    
82. }

复制代码