17. 电话号码的字母组合
难度中等
2474
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4digits[i] 是范围 ['2', '9'] 的一个数字。
通过次数696,168提交次数1,198,761
题解：
我们先定义了一个字母表，将数字映射到对应的字母组合上。接着定义了一个结果集合result。在函数letterCombinations中，我们首先判断特殊情况，如果数字串为空，则返回空列表。否则，我们开始递归调用回溯函数backtrack。
在回溯函数中，我们首先判断是否已经到达数字串的末尾，如果到达，则将当前的组合字符串加入结果集合中。否则，我们取出当前数字所对应的字母组合，对于每一个字母，都将其加入到组合字符串中，并递归调用backtrack函数，最后将该字母从组合字符串中删除（回溯到上一步）。
这样，当回溯函数返回时，我们就可以得到所有的字母组合了。
class Solution {
private val letterMap = arrayOf("", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz")
private val result = mutableListOf
fun letterCombinations(digits: String): List
if (digits.isEmpty()) {
return emptyList()
}
backtrack(digits, 0, StringBuilder())
return result
}
private fun backtrack(digits: String, index: Int, combination: StringBuilder) {
if (index == digits.length) {
result.add(combination.toString())
return
}
val digit = digits[index].toString().toInt()
val letters = letterMap[digit]
for (i in letters.indices) {
combination.append(letters[i])
backtrack(digits, index + 1, combination)
combination.deleteCharAt(combination.length - 1)
}
}
}
回溯法属于暴力求解，有趣的是，竟然做到了不重不漏，虽然是穷举，将符合情况的结果全部都收集起来。如果全部掌握了回溯法，那么数独这个游戏就变得毫无意义了。
相关文章
您阅读本篇文章共花了：
发表评论