[LeetCode] 17. Letter Combinations of a Phone Number（手机的 T9 输入法）

2022-05-11 03:26:58

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)
        }
    }
}