17.letter Combinations of a Phone Number

题目

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent.

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

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

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

Note:

Although the above answer is in lexicographical order, your answer could be in any order you want.

尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

分析

对于结果可以通过深度优先或者广度优先来处理。

func letterCombinationsDFS(digits string) []string {
	var jp = []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
	cur := make([]rune, len(digits))
	ans = dfs(digits, jp, 0, cur)
	return ans
}

var (
	ans []string
)

func dfs(digits string, jp []string, l int, cur []rune) []string {

	if l == len(digits) {
		if l > 0 {
			ans = append(ans, string(cur))
		}
		return ans
	}
	s := jp[digits[l]-'0']
	for _, v := range s {
		cur[l] = v
		fmt.Println("cur:", string(cur))
		ans = dfs(digits, jp, l+1, cur)
	}
	return ans
}

func letterCombinations(digits string) []string {
	var jp = []string{"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"}
	ld := len(digits)
	// 初始化
	r := []string{}
	if ld == 0 {
		return r
	}
	r = []string{""}
	for i := 0; i < ld; i++ {
		var tmp []string
		// 获取jp对应的下标
		index := digits[i] - '0'
		for _, k := range r {
			for _, j := range jp[index] {
				tmp = append(tmp, k+string(j))
			}
		}
		// 重新给r赋值
		r = tmp
	}
	return r
}

我的名字叫浩仔/17.letter Combinations of a Phone Number

题目

分析