leetcode17 Letter Combinations of a Phone Number

snowell 发布于2019-08-14 18:09 / 2918人阅读

摘要：题目要求也就是说，将数字对应的字母的排列组合的的所有可能结果都枚举出来，顺序不唯一。这种类型的题目一般需要求出上一种情况的前提下才可以得知下一种情况。这一种数据结构通过来实现。相比于上一种思路中，内存占用更小，而且更加灵活。

题目要求

Given a digit string, 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.

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

Note:
Although the above answer is in lexicographical order, your answer could be in any order you want.

也就是说，将数字对应的字母的排列组合的的所有可能结果都枚举出来，顺序不唯一。

leetcode给这道题目加了一个标签很有意思，叫做Backtracking。点进去之后又很多类似的题目。这种类型的题目一般需要求出上一种情况的前提下才可以得知下一种情况。比如我必须先得知按下“2”后所有字母的可能值，才能在计算出“22”对应的可能值

思路一：递归

当我们无法直接得出结果的时候，我们可以借助递归让计算机帮我们考虑每一种情况并逐级得出当前的结果。在本思路中，我用了String数组来表示每一个按键对应的字母，其中数组的下标代表按键值。

    String[] letters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List letterCombinations(String digits) {
        List result = new ArrayList();
        for(int i = 0 ; i letterCombinations(char digit, List currentList){
        int number = digit - "0";
        String letter = letters[number];
        if(letter.length()==0){
            return currentList;
        }
        
        if(currentList.size() == 0){
            for(int i = 0 ; i result = new ArrayList();
        for(int i = 0 ; i
思路二：队列（通过linkedlist实现）
从队列头获得上一种情况的结果，经过处理后添加到队列尾。这一种数据结构通过linkedList来实现。相比于上一种思路中ArrayList，linkedList内存占用更小，而且更加灵活。
    String[] letters = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    public List letterCombinations2(String digits) {
        LinkedList l = new LinkedList();
        if(digits.length()==0){
            return l;
        }
        l.add("");
        
        int empty = 0;
        for(int i = 0 ; i < digits.length() ; i++){
            int number = digits.charAt(i) - "0";

            String letter = letters[number];
            if(letter.length() == 0){
                empty++;
                continue;
            }
            while(l.peek().length() + empty == i){
                String peek = l.removeFirst();
                for(int j = 0 ; j

想要了解更多开发技术，面试教程以及互联网公司内推，欢迎关注我的微信公众号！将会不定期的发放福利哦~

私有云云服务器 Combinations Letter automation of com first-letter

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/67027.html

leetcode 17 Letter Combinations of a Phone Number

摘要：而按键和字母的对应关系如上图。这将成为下一次操作的前序字符串。对于每一个不同的前序字符串，我们都要在其后面分别加上当前键所表示的不同字符，再将获得的结果字符串加入里面。题目详情 Given a digit string, return all possible letter combinations that the number could represent. mapping o...

sean 2019-08-15 14:39 评论0 收藏0
[Leetcode] Letter Combinations of a Phone Number 电

摘要：最新更新请见深度优先搜索复杂度时间空间递归栈空间思路首先建一个表，来映射号码和字母的关系。然后对号码进行深度优先搜索，对于每一位，从表中找出数字对应的字母，这些字母就是本轮搜索的几种可能。 Letter Combinations of a Phone Number 最新更新请见：https://yanjia.me/zh/2019/01/... Given a digit string...

fxp 2019-08-14 12:34 评论0 收藏0
leetcode 部分解答索引（持续更新～）

摘要：前言从开始写相关的博客到现在也蛮多篇了。而且当时也没有按顺序写现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言从开始写leetcode相关的博客到现在也蛮多篇了。而且当时也没有按顺序写～现在翻起来觉得蛮乱的。可能大家看着也非常不方便。所以在这里做个索引嘻嘻。顺序整理 1~50 1...

leo108 2019-08-15 14:26 评论0 收藏0
记一次作死 —— 被 Leetcode 封禁

摘要：不过好消息是，在事件发生的二十四小时以后，我发现我的账号解禁了，哈哈哈哈。本文最初发布于我的个人博客：咀嚼之味从昨天凌晨四点起，我的 Leetcode 账号就无法提交任何代码了，于是我意识到我的账号大概是被封了…… 起因我和我的同学 @xidui 正在维护一个项目 xidui/algorithm-training。其实就是收录一些算法题的解答，目前主要对象就是 Leetcode。...

dackel 2019-08-19 17:06 评论0 收藏0
九宫格键盘输入

摘要：九宫格键盘输入给定一个数字字符串，返回数字可能代表的所有可能的字母组合。数字到字母的映射就像九宫格电话按钮一样如下图。思路以为例，代表，只需要将其转换成，然后处理，为，将这三个字符分别加到的每一个元素中，得到。重复此过程即可。九宫格键盘输入 Letter Combinations of a Phone Number 给定一个数字字符串，返回数字可能代表的所有可能的字母组合。数字到...

Xufc 2019-07-25 12:04 评论0 收藏0