17.电话号码的字母组合.md

17. 电话号码的字母组合

url

题目

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
输入：digits = ""
输出：[]
输入：digits = "2"
输出：["a","b","c"]

方法

code

js

let letterCombinations = digits => {
    let dfs = (digits, sb) => {
        if (sb.length === digits.length) {
            ret.push(sb);
            return;
        }
        let c = digits[sb.length] - '0';
        let cur = KEYS[c];
        for (const a of cur) {
            sb += a;
            dfs(digits, sb);
            sb = sb.substring(0, sb.length - 1);
        }
    };
    let KEYS = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"];
    let ret = [];
    if (digits === null || digits.length === 0)
        return ret;
    dfs(digits, "");
    return ret;
};

go

func letterCombinations(digits string) []string {
	var KEYS = []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
	var res []string
	var dfs func(digits string, sb string)
	if len(digits) == 0 {
		return res
	}
	dfs = func (digits string, sb string) {
		if len(sb) == len(digits) {
			res = append(res, sb)
			return
		}
		c := digits[len(sb)] - byte('0')
		cur := KEYS[c]
		for _, v := range cur {
			sb += string(v)
			dfs(digits, sb)
			sb = sb[0:len(sb) - 1]
		}
	}
	dfs(digits, "")
	return res
}

java

class Solution {
    private static final String[] KEYS = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    List<String> ret = new ArrayList<>();
    public List<String> letterCombinations(String digits) {        
        if(digits == null || digits.length() == 0) return ret;
        dfs(digits, new StringBuilder());
        return ret;
    }
    
    private void dfs(String digits, StringBuilder sb) {
        if (sb.length() == digits.length()){
            ret.add(sb.toString());
            return;
        }
        int c = digits.charAt(sb.length()) - '0';
        String cur = KEYS[c];
        for (char a : cur.toCharArray()){
            sb.append(a);
            dfs(digits, sb);
            sb.deleteCharAt(sb.length() - 1);
        }
    
    }
}