Question:
My code:
import java.util.ArrayList;
import java.util.List;
public class Solution {
public List<String> letterCombinations(String digits) {
if (digits == null)
return null;
String[] phone = {" ", "", "abc", "def", "ghi", "jkl", "mno",
"pqrs", "tuv", "wxyz"};
List<String> result = new ArrayList<String>();
if (digits.length() == 0) {
return result;
}
String character = "";
getStr(result, phone, digits, character);
return result;
}
private void getStr(List<String> result, String[] phone, String digits, String character) {
if (digits.length() == 0) {
result.add(character);
return;
}
int id = digits.charAt(0) - 48;
int len = phone[id].length();
for (int i = 0; i < len; i++)
getStr(result, phone, digits.substring(1, digits.length()), character + phone[id].charAt(i));
}
public static void main(String[] args) {
Solution test = new Solution();
String a = "23";
System.out.println(test.letterCombinations(a));
}
}
My test result:
![Upload Paste_Image.png failed. Please try again.]
好久没写递归了。一开始也没想到递归，想的是用循环。然后一个个的加上去。
后来发现不行。
**
总结：循环的话，他有一个特点，他是一个稳定状态机，然后会按照固定的，唯一的状态，进行下去。更加严谨的说，下一个状态由上一个状态唯一的确定，不会出现多种可能发生的情况。
像这道题目，按1，会有 abc。 按2，会有 def。 那么按1之后按2，发生的状态就不能确定。这层状态不能确定，那么下层状态的先决条件，也就是该状态就不能确定。她会如同 树木一样分支开花，走出多种可能性。
面对这种情况，就需要用递归。就是DFS的思想。
去吃饭了。
**
Anyway, Good luck, Richardo!
My code:
public class Solution {
public List<String> letterCombinations(String digits) {
ArrayList<String> ret = new ArrayList<String>();
if (digits == null || digits.length() == 0)
return ret;
String[] arr = {" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
helper(0, digits, "", arr, ret);
return ret;
}
private void helper(int index, String digits, String s, String[] arr, ArrayList<String> ret) {
if (index >= digits.length()) {
ret.add(s);
return;
}
else {
char curr = digits.charAt(index);
int offset = curr - 48;
if (offset == 1)
helper(index + 1, digits, s, arr, ret);
else {
for (int i = 0; i < arr[offset].length(); i++) {
helper(index + 1, digits, s + arr[offset].charAt(i), arr, ret);
}
}
}
}
}
一开始不知道 1 代表了什么。后来知道表示 "" ， 思路就很清晰了。
Anyway, Good luck, Richardo!
My code:
public class Solution {
String[] strs = new String[]{" ", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {
List<String> ret = new ArrayList<String>();
if (digits == null || digits.length() == 0) {
return ret;
}
helper(0, digits, new StringBuilder(), ret);
return ret;
}
private void helper(int index, String digits, StringBuilder path, List<String> ret) {
if (index >= digits.length()) {
ret.add(path.toString());
return;
}
char curr = digits.charAt(index);
String s = strs[curr - '0'];
int len = path.length();
for (int i = 0; i < s.length(); i++) {
path.append(s.charAt(i));
helper(index + 1, digits, path, ret);
path.setLength(len);
}
}
}
相比于以前的改进是， 改用了 StringBuilder, 速度更快。
注意：
1 . 以后有这种枚举类型的dfs，可以申明全局变量来表示所有的状态。
比如这里的 0-9 是个按键对应的字母
还有，图中运动起来的四个方向。
将会让代码变得更加简洁
2 . 用 StringBuilder 来做 backtracking,需要回删，
这个时候一般的操作是，在 dfs之前，先记录下stringbuilder 原长度。
int len = sb.length();
然后，backtracking 回来时，删除之前的状态， 就这么写：
sb.setLength(len);
差不多的就这个思路。
Anyway, Good luck, Richardo! -- 09/17/2016
