首页
编程语言

分类

当前位置: 云海天教程网 > 技术新闻 > 编程语言 >正文

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

更新时间:2020-11-21  作者:佚名   来源:网络转载


	[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 没有映射到任何字母。


	[LeetCode] 17. Letter Combinations of a Phone Number(手机的 T9 输入法)
[编程语言教程]

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

上一篇: 【codeforce】#682 T1 [随笔记录] 下一篇: Codeforces Round #677 (Div. 3) [随笔记录]
小编推荐
快速导航更多>>
JavaScript 教程 HTML5 教程 CSS3 教程 jQuery 教程 Vue.js 教程 Node.js 教程 SQL 教程 C 教程 PHP 教程 Linux 教程 Docker 教程 Nginx 教程 Python 教程 Java 教程

云海天教程网 版权所有

陕ICP备14013131号-3