首页 > 代码库 > Leetcode: Letter Combinations of a Phone Number

Leetcode: Letter Combinations of a Phone Number

像这种DFS的题目,常见的写法无外乎两种,使用recursion, 或者用Stack。本文采用了stack的方式。做完后积累的经验有:像这种在一个ArrayList里面罗列可能的path的题目,recursion的参数一般包括:包含最终结果的集合(ArrayList),input(String),递归层次level(int),某一条具体的path(String)。最后这个参数虽然不是必须,但是如果使用了它,将会使recursion非常好写:所有关于这条路径的添加、删除、修改都可以以这个具体的path为操作对象,并且一旦条件满足,就可以把这个path添加到最终的结果集合里面去,用ArrayList add函数

还有一些细节需要注意:用switch函数的时候,要记得写break,否则所有的case都会执行

 1 public class Solution {
 2     public ArrayList<String> letterCombinations(String digits) {
 3         ArrayList<String> res = new ArrayList<String>();
 4         getlist(digits, res, "", 0);
 5         return res;
 6     }
 7     
 8     public void getlist(String digits, ArrayList<String> res, String single, int level) {
 9         if (digits.length() == single.length()) {
10             res.add(single);
11             return;
12         }
13         int c = (int)(digits.charAt(level) - ‘0‘); //get the specific digit at the level unit
14         String temp = possible(c);
15         char[] letterpool = temp.toCharArray();
16         for (char st : letterpool) {
17             single += st;
18             getlist(digits, res, single, level+1);
19             single = single.substring(0, single.length() - 1);
20         }
21     }
22     
23     public String possible(int c) {
24         String letters = "";
25         switch (c) {
26             case 2: letters = "abc"; break;
27             case 3: letters = "def"; break;
28             case 4: letters = "ghi"; break;
29             case 5: letters = "jkl"; break;
30             case 6: letters = "mno"; break;
31             case 7: letters = "pqrs"; break;
32             case 8: letters = "tuv"; break;
33             case 9: letters = "wxyz"; break;
34             case 0: letters = " "; break;
35         }
36         return letters;
37     }
38 }