[LeetCode] 17. Letter Combinations of a Phone Number(手机的 T9 输入法)
-
Difficulty: Medium
-
Related Topics: String, Backtracking
-
Link: https://leetcode.com/problems/letter-combinations-of-a-phone-number/
Description
Given a string containing digits from 2-9
inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.
给定一个包含数字 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 没有映射到任何字母。
Examples
Example 1
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]
Example 2
Input: digits = ""
Output: []
Example 3
Input: digits = "2"
Output: ["a","b","c"]
Constraints
0 <= digits.length <= 4
digits[i]
is a digit in the range[‘2‘, ‘9‘]
.
Solution
这次的回溯法应该属于组合型的类型,代码如下:
class Solution {
private val digitToLetter = mapOf(
‘2‘ to "abc",
‘3‘ to "def",
‘4‘ to "ghi",
‘5‘ to "jkl",
‘6‘ to "mno",
‘7‘ to "pqrs",
‘8‘ to "tuv",
‘9‘ to "wxyz"
)
fun letterCombinations(digits: String): List<String> {
if (digits.isBlank()) {
return emptyList()
}
val result = arrayListOf<String>()
backtrack(digits, 0, "", result)
return result
}
private fun backtrack(digits: String, curIndex: Int, curWord: String, result: MutableList<String>) {
if (curWord.length == digits.length) {
result.add(curWord)
return
}
for (letter in digitToLetter[digits[curIndex]]?:"") {
backtrack(digits, curIndex + 1, curWord + letter, result)
}
}
}
[LeetCode] 17. Letter Combinations of a Phone Number(手机的 T9 输入法)
原文地址:https://www.cnblogs.com/zhongju/p/13997869.html
hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » [LeetCode] 17. Letter Combinations of a Phone Number(手机的 T9 输入法)
自学咖网 » [LeetCode] 17. Letter Combinations of a Phone Number(手机的 T9 输入法)