Question:

Paste_Image.png

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.]

好久沒寫遞歸了。一開始也沒想到遞歸，想的是用循環(huán)。然后一個個的加上去。
后來發(fā)現(xiàn)不行。

**
總結：循環(huán)的話，他有一個特點，他是一個穩(wěn)定狀態(tài)機，然后會按照固定的，唯一的狀態(tài)，進行下去。更加嚴謹?shù)恼f，下一個狀態(tài)由上一個狀態(tài)唯一的確定，不會出現(xiàn)多種可能發(fā)生的情況。
像這道題目，按1，會有 abc。 按2，會有 def。 那么按1之后按2，發(fā)生的狀態(tài)就不能確定。這層狀態(tài)不能確定，那么下層狀態(tài)的先決條件，也就是該狀態(tài)就不能確定。她會如同 樹木一樣分支開花，走出多種可能性。
面對這種情況，就需要用遞歸。就是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，可以申明全局變量來表示所有的狀態(tài)。
比如這里的 0-9 是個按鍵對應的字母
還有，圖中運動起來的四個方向。
將會讓代碼變得更加簡潔
2 . 用 StringBuilder 來做 backtracking,需要回刪，
這個時候一般的操作是，在 dfs之前，先記錄下stringbuilder 原長度。

int len = sb.length();

然后，backtracking 回來時，刪除之前的狀態(tài)， 就這么寫：

sb.setLength(len);

差不多的就這個思路。

Anyway, Good luck, Richardo! -- 09/17/2016