Letter Combinations of a Phone Number

Leave a comment

October 31, 2016 by oneOokay

DFS+backtracking和Queue.

两个java基本的知识点:

StringBuffer:

sb.deleteCharAt(sb.length() - 1) 或者
sb.setLength(sb之前的length)

把一个char形式的数字转换回真正的数字的方法:

  • c – ‘0’
  • Character.getNumericValue(char)
  • Integer.parseInt(String.valueOf(d.charAt(index))) :这个比较绕还是不用比较好.

以及能用array存就尽量用array,不要用hashmap.


先看DFS, 如何DFS?

  • 很容易想到需要两个循环,一个循环digits本身,一个循环每一个digit所对应的char.
  • 这两个循环都放哪里?怎么循环?
  • 写了一个错误的:
    • main method里面: dfs(0, “”):
    • dfs里面两个for loop:第一个loop digits,第二个loop chars 再继续dfs(i + 1, newString).
    • 当index == digits.length()的时候加入到res里面.
  • 错在哪里?错在这个会把newString长度小于digits.length()的结果也放到res里面.为什么?因为会跳过index. dfs(0, “”)的时候是正确的,但是dfs里面loop digits的时候,当它loop到index =2的时候,此时原string还是””,那接下来就直接跳过了第一位,从第二位开始往上加了. 而题目是要求所有digits的所有都取.不能跳过.
  • 所以. for loop digits也不能放到main method里面,也会跳过元素. 那么怎么loop digits? 在dfs里面loop.
  • dfs(index, str) 传入当前处理的digit index. 一个for loop 给当前digit index所对应的char, 对每一个char,dfs(index+1, str+c). 这样想象成是从第一个digits开始的一个树, 在每一个叶子上面都有根的值在,就不会漏掉了.
  • dfs的时候不用backtracking, 加上再减去比较麻烦.传入s+c,这样当前层的s并没有发生变化.
private List res;
    private char[] chs;
    private String[] strs;
    private int len;
    public List letterCombinations(String digits) {
        res = new ArrayList<>();
        if (digits == null || digits.length() == 0) return res;
        chs = digits.toCharArray();
        strs = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        len = digits.length();
        dfs(0, "");
        return res;
    }
    
    private void dfs(int index, String s){
        if(index == len){
            res.add(s);
            return;
        }
        int cur = chs[index] - '0';
//一个for loop through chars
        for(int i = 0; i < strs[cur].length(); i ++){
            dfs(index + 1, s + strs[cur].charAt(i));    
        }
    }

 


来看一下BFS的方法:

  • e.g.: 23
  • for loop第一次循环产生:a,b,c; 放到queue里面
  • for loop第二次就从queue里面poll出来每一个string后面分别加上def, 生成新的string放入到queue里面.
  • 首先容易想到的是用cur 和 next来轮回的方法记录当前queue头上的string是当前需要处理的还是已经加上过char的.
  • 这里用了一个trick就是,如果当前queue peek的length和i是一样的话,说明还没有加上c,要继续处理.
  public List<String> letterCombinations(String digits) {
 List<String> res = new ArrayList<>();
 if (digits == null || digits.length() == 0) return res;
 String[] strs = new String[]{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
 Queue<String> queue = new LinkedList<>();
 queue.offer("");
 int index = 0;
 String s = "";
 for(int i = 0; i < digits.length(); i ++){
 index = digits.charAt(i) - '0';
 while(queue.peek().length() == i){
 s = queue.poll();
 for(int j = 0; j < strs[index].length(); j ++){
 queue.offer(s + strs[index].charAt(j)); 
 }
 }
 }
 
 while(!queue.isEmpty()){
 res.add(queue.poll());
 }
 return res;
 }
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s

%d bloggers like this: