Letter Combinations of a Phone Number

Leave a comment

October 31, 2016 by oneOokay

两种方法:DFS+backtracking和Queue. DFS的已经能够顺利做出来了.

两个java基本的知识点:

StringBuffer:

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

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

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

以及能用array存就尽量用array,不要用hashmap. array在这个index取值方面高一些???

来看一下queue的方法:

  • e.g.: 23
  • for loop第一次循环产生:a,b,c
  • for loop第二次就:ad,ae,af; bd,be,bf;cd,ce,cf.
    public List letterCombinations(String digits) {
        LinkedList ans = new LinkedList();
        if (digits == null || digits.length() == 0) return ans;
        String[] keys = new String[]{"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        ans.add("");
        for (int i = 0; i < digits.length(); i ++){
            int index = Character.getNumericValue(digits.charAt(i));
            while (ans.peek().length() == i){
                String str = ans.remove();
                for (char c : keys[index].toCharArray()){
                    ans.add(str + c);
                }
            }
        }
        return ans;
    }

DFS:

public class Solution {
private static String[] strs = {"", "", "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
private List ans;
private static String d;
public List letterCombinations(String digits) {
ans = new ArrayList();
if (digits == null || digits.isEmpty()){
return ans;
}
d = digits;
StringBuilder sb = new StringBuilder();
dfs(0, sb);
return ans;
}

private void dfs(int index, StringBuilder sb){
if (index == d.length()){ //重温一下dfs:这里是把一个解加入ans所需要符合的条件
ans.add(new String(sb));
return;
}

String target = strs[Integer.parseInt(String.valueOf(d.charAt(index)))]; //注意这一块的转换:以char形式出现的integer 转成 interger的方法。。。
for (int i = 0; i < target.length(); i ++) {
sb.append(target.charAt(i));
dfs(index + 1, sb);
sb.deleteCharAt(sb.length() - 1); //stringBuilder
}
}
}

 

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: