算法练习--LeetCode--17. Letter Combinations of a Phone Numbe

发布时间：2020-12-14 05:16:50 所属栏目：大数据来源：网络整理

导读：Letter Combinations of a Phone Number Medium Given a string containing digits from? 2-9 ?inclusive,return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons)

Letter Combinations of a Phone Number
Medium

Given a string containing digits from?2-9?inclusive,return all possible letter combinations that the number could represent.

A mapping of digit to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

1o-o_?2abc?3def
4ghi_?5jkl?6mno
7pqrs?8tuv?9wxyz
*+___?0___?#↑__

除了0的第一个“”以外的位置的“”是为了对齐

?

我觉得上面那玩意儿不如图

Example:

Input:?"23"
Output:?["ad","ae","af","bd","be","bf","cd","ce","cf"]

大意是指要把输入的数字按照手机键盘的映射关系转成可能的字符串

不要有重复的
不用在意字符串顺序（输出结果数组的排序）

Note:

虽然题目中给出输入数字在[2,9]，实测(2019-01-05)?0和1也有对应的映射关系

0 => " "
1 => "*"

基本分析：

要求长度为n的结果，首先要求长度为n-1的结果！
n == 1 时候结果是已知的

        "0" : [" "],"1" : ["*"],"2" : ["a","b","c"],"3" : ["d","e","f"],"4" : ["g","h","i"],"5" : ["j","k","l"],"6" : ["m","n","o"],"7" : ["p","q","r","s"],"8" : ["t","u","v"],"9" : ["w","x","y","z"]

为了节约时间要有缓存

基本思路

func letterCombinations(s: String) -> [String] {
  if s 为空字符串， return 空数组
    if cache 不包含 s {
      cache[s] = cache[s的第一个字符] * letterCombinations(s除了第一字符以外剩下的部分的结果)
    }
  return cache[s]
}

代码

// Swift Code
class Solution {
    var cache: [String : [String]] = [
        "0" : [" "],"z"]
    ]

    func letterCombinations(_ digits: String) -> [String] {
        if digits.isEmpty { return [] }
        if !cache.keys.contains(digits) {
            cache[digits] = letterCombinations(String(digits.prefix(1))).flatMap({ (s) -> [String] in
                letterCombinations(String(digits.suffix(digits.count - 1))).map { s + $0 }
            })
        }
        return cache[digits]!
    }
}

TestCase

""
"23"
"203"
"213"

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!