电话号码组合

电话号码组合

难度：中等
问题描述：
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。给出数字到字母的映射如下（与电话按键相同）。【注意 1 不对应任何字母】

号码键盘图如下所示：

示例 ：

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

链接：原题链接

解法

解法1：穷举法

• 思路：
  对于 N 位输入，总组合 = 前 N-1 位的组合 * 第 N 位可能的值（即: 前 N-1 的组合中的每一个元素均和第 N 位元素相结合，便是 N 位输入的所有组合，以此类推。）
• 代码：

  func letterCombinations(digits string) []string {
  	// 用字典把手机号码和字母对应起来
  	lettersMap := map[string][]string{
  		"2":{"a", "b", "c"},      // 2
  		"3":{"d", "e", "f"},      // 3
  		"4":{"g", "h", "i"},      // 4
  		"5":{"j", "k", "l"},      // 5
  		"6":{"m", "n", "o"},      // 6
  		"7":{"p", "q", "r", "s"}, // 7
  		"8":{"t", "u", "v"},      // 8
  		"9":{"w", "x", "y", "z"}, // 9
  	}
  
  	// 输入的长度
  	lengthDigits := len(digits)
  	// 用于存所有组合的切片
  	var combinationsList []string
  
  	// 如果输入为空，直接返回。若不为空，先填充第一个元素的组合
  	if len(digits) ==0 {
  		return []string{}
  	}else {
  		for _, v := range lettersMap[string(digits[0])] {
  		combinationsList = append(combinationsList, v)
  		}
  	}
  
  	// 穷举出剩下的所有元素的所有组合
  	for i := 1; i < lengthDigits; i++ {
  		// 遍历 combinationsList 的每个元素, 并将 lettersMap[string(digits[i])] 字母挨个加入其元素尾部
  		lenList := len(combinationsList)
  		for _, v1 := range  combinationsList {
  			var list []string
  			for _, v2 := range lettersMap[string(digits[i])] {
  				list = append(list, v1 + v2)
  			}
  			// 前 i 个输入的组合全部在 combinationsList 的尾部
  			combinationsList = append(combinationsList, list...)
  		}
  		// combinationsList 前 lenList 个元素表示的是前 i-1 的所有组合，因此需要将前 lenList 个元素删除
  		combinationsList =  combinationsList[lenList:]
  	}
  	return combinationsList
  }

  时间复杂度：O((n+m)(3^n)(4^m)), 其中 n 是输入中对应字母为3的个数，m 是输入中对应字母为4的个数
  空间复杂度：O((3^n)(4^m))

解法2：递归法

• 思路：对于解法一的思路，递归法的实现
• 代码：

  func letterCombinationsWithRecursion(digits string) []string {
  	var lettersMap = map[string][]string{
  		"2":{"a", "b", "c"},      // 2
  		"3":{"d", "e", "f"},      // 3
  		"4":{"g", "h", "i"},      // 4
  		"5":{"j", "k", "l"},      // 5
  		"6":{"m", "n", "o"},      // 6
  		"7":{"p", "q", "r", "s"}, // 7
  		"8":{"t", "u", "v"},      // 8
  		"9":{"w", "x", "y", "z"}, // 9
  	}
  
  	var combinationsList []string
  
  	if len(digits) == 0 {
  		return []string{}
  	}
  	recursion(digits, 0, "", lettersMap, &combinationsList)
  	return combinationsList
  }
  
  func recursion(digits string, index int, combination string, lettersMap  map[string][]string, combinationsList *[]string)  {
  	if index == len(digits){
  		*combinationsList = append(*combinationsList, combination)
  	}else {
  		letters := lettersMap[string(digits[index])]
  		length := len(letters)
  		for i := 0; i < length; i++ {
  			recursion(digits, index+1, combination + letters[i], lettersMap, combinationsList)
  		}
  	}
  }

  时间复杂度：O((3^m)(4^n))， 其中 n 是输入中对应字母为3的个数，m 是输入中对应字母为4的个数
  空间复杂度：O(m+n)