讨论/《深度优先搜索》 - 练习:电话号码的字母组合/
《深度优先搜索》 - 练习:电话号码的字母组合
共 2 个回复
func letterCombinations(digits string) []string {
	result := []string{}
	if len(digits) == 0 {
		return result
	}

	d2s := make(map[byte][]string, 0)
	d2s['2'] = []string{"a", "b", "c"}
	d2s['3'] = []string{"d", "e", "f"}
	d2s['4'] = []string{"g", "h", "i"}
	d2s['5'] = []string{"j", "k", "l"}
	d2s['6'] = []string{"m", "n", "o"}
	d2s['7'] = []string{"p", "q", "r", "s"}
	d2s['8'] = []string{"t", "u", "v"}
	d2s['9'] = []string{"w", "x", "y", "z"}

	var dfs func(i int, path string)
	dfs = func(i int, path string) {
		if i >= len(digits) {
			result = append(result, path)
			return
		}
		for _, v := range d2s[digits[i]] {
			path = path + v
			dfs(i+1, path)
			path = path[:len(path)-1]
		}
	}
	dfs(0, "")
	return result
}
class Solution:
    def letterCombinations(self, ds: str) -> List[str]:
        res = []
        phone = {'2':['a','b','c'],
                 '3':['d','e','f'],
                 '4':['g','h','i'],
                 '5':['j','k','l'],
                 '6':['m','n','o'],
                 '7':['p','q','r','s'],
                 '8':['t','u','v'],
                 '9':['w','x','y','z']}
        def btk(pth,ds):
            if not ds:
                res.append(pth)
                return
            for c in phone[ds[0]]:
                btk(pth + c,ds[1:])
        btk('',ds)
        return res if ds else []