[LeetCode] 017. Letter Combinations of a Phone Number (Medium) (C++/Java/Python)

索引：[LeetCode] Leetcode 题解索引 (C++/Java/Python/Sql)
Github: https://github.com/illuz/leetcode

017.Letter_Combinations_of_a_Phone_Number (Medium)

链接：

题目：https://oj.leetcode.com/problems/letter-combinations-of-a-phone-number/
代码(github)：https://github.com/illuz/leetcode

题意：

在手机上按字母，给出按的数字键，问所有的按的字母的情况。

分析：

DFS 过去是比较轻松的写法。

代码：

C++:

class Solution {
private:
	const string alpha[10] = {
		" ",
		"1", "abc", "def",
		"ghi", "jkl", "mno",
		"pqrs", "tuv", "wxyz"
	};
	void dfs(vector<string> &res, string &ab, string &digits, int cur) {
		if (cur >= digits.length()) {
			res.push_back(ab);
			return;
		}
		for (auto &a : alpha[digits[cur] - '0']) {
			ab.push_back(a);
			dfs(res, ab, digits, cur + 1);
			ab.pop_back();
		}
	}
public:
    vector<string> letterCombinations(string digits) {
		vector<string> res;
		string alphas;
		dfs(res, alphas, digits, 0);
		return res;
    }
};

Java:

public class Solution {
    private String[] alpha = new String[] {
            " ",
            "1", "abc", "def",
            "ghi", "jkl", "mno",
            "pqrs", "tuv", "wxyz"
    };
    private StringBuilder word;

    private void dfs(List<String> res, String digits, int cur) {
        if (cur >= digits.length()) {
            res.add(word.toString());
        } else {
            for (int i = 0; i < alpha[digits.charAt(cur) - '0'].length(); ++i) {
                word.append(alpha[digits.charAt(cur) - '0'].charAt(i));
                dfs(res, digits, cur + 1);
                word.deleteCharAt(word.length() - 1);
            }
        }
    }

    public List<String> letterCombinations(String digits) {
        List<String> ret = new ArrayList<String>();
        word = new StringBuilder();
        dfs(ret, digits, 0);
        return ret;
    }
}

Python:

class Solution:
    # @return a list of strings, [s1, s2]
    def letterCombinations(self, digits):
        alpha = [" ", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
        res = []
        word = []
        def dfs(cur):
            if cur >= len(digits):
                res.append(''.join(word))
            else:
                for x in alpha[(int)(digits[cur]) - (int)('0')]:
                    word.append(x)
                    dfs(cur + 1)
                    word.pop()
        dfs(0)
        return res