17. 电话号码的字母组合

题目描述:

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。


image.png

示例:

输入:"23"
输出:["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:

尽管上面的答案是按字典序排列的,但是你可以任意选择答案输出的顺序。

思路-回溯法:

回溯是一种通过穷举所有可能的情况来找到解的算法。
定义回溯函数:backtrack(combination, next_digits) ,它将一个目前已经产生的组合combination,和接下来准备要输入的数字字符串next_digits作为参数。
如果没有更多的数字(已经遍历完了所有数字),那就意味着当前的组合已经产生了。将combination添加到组合ans中即可
如果还要数字被输入,则遍历下一个数字对应的每个字母letter:
将当前的字母添加到组合的最后,也就是说combination = combination + letter ,
重复上述过程,继续遍历剩下的数字:backtrack(combination + letter, next_digits[1:]) 。

Java解法:

class Solution {
    Map<String, String> map = new HashMap<String, String>() {{
        put("2", "abc");
        put("3", "def");
        put("4", "ghi");
        put("5", "jkl");
        put("6", "mno");
        put("7", "pqrs");
        put("8", "tuv");
        put("9", "wxyz");
  }};
    List<String> ans = new ArrayList<String>();
    public void backtrack(String combination, String next_digit)
    {
        int len = next_digit.length();
        if (len == 0)
        {
            ans.add(combination);
        }else{
            String digit = next_digit.substring(0, 1);
            String letters = map.get(digit);
            for(int i = 0; i < letters.length(); i++)
            {
                String curletter = map.get(digit).substring(i, i+1);
                backtrack(combination + curletter, next_digit.substring(1));
            }
        }
    }
    public List<String> letterCombinations(String digits) {
        if (digits.length() != 0)
        {
            backtrack("", digits);
        }
        return ans;
    }
}
image.png

python3解法:

class Solution:
    def letterCombinations(self, digits: str) -> List[str]:
        dic = {
            '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']
        }
        def backtrack(combination, left_digits):
            # 当数字字符串已经遍历完时,即 backtrack('ad','')
            if not left_digits:
                ans.append(combination)
            #遍历当前数字对应的字符串,例如2,对应a,b,c
            for letter in dic[left_digits[0]]:
                #也就是backtrack('a', '3'),backtrack('b', '3'),backtrack('c', '3')
                backtrack(combination + letter, left_digits[1:])
        # 存储所有字母组合
        ans = []
        if digits:
            backtrack('', digits)
        return ans

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problemset/all/

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 钱是什么,钱能使人快乐,但是不能帮你消除所有的烦恼。最近的我很烦恼,特别需要钱来让我快乐。 我的宝宝春节后出生了,...
    胖园说阅读 358评论 0 1
  • 01 "你最近都没出去玩吗?怎么都没见你的朋友圈动态了"朋友A问我 “这几天人间蒸发了吗?怎么一个泡也不冒了"B同...
    sjj会飞的蒲公英阅读 874评论 6 4
  • 有朋友问我,怎么你们女生都变得越来越强悍了啊? 特别是你们这些长得娇小的,看着人小小只,居然比我们男生还强悍。 你...
    情感小贴士ff阅读 177评论 0 1
  • 前几天读了一本日本作者的书,书名不记得了,大致是如何让你牢牢记住所看的东西,是在图书馆穿行走向自己座位的时候无意间...
    麻辣烫加麻酱阅读 1,000评论 0 0