[Leetcode] Letter Combinations of a Phone Number 电

fxp 发布于2019-08-14 12:34 / 2514人阅读

摘要：最新更新请见深度优先搜索复杂度时间空间递归栈空间思路首先建一个表，来映射号码和字母的关系。然后对号码进行深度优先搜索，对于每一位，从表中找出数字对应的字母，这些字母就是本轮搜索的几种可能。

Letter Combinations of a Phone Number 最新更新请见：https://yanjia.me/zh/2019/01/...

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.

深度优先搜索 复杂度

时间 O(N) 空间 O(N) 递归栈空间

思路

首先建一个表，来映射号码和字母的关系。然后对号码进行深度优先搜索，对于每一位，从表中找出数字对应的字母，这些字母就是本轮搜索的几种可能。

注意

用StringBuilder构建临时字符串

当临时字符串为空时，不用将其加入结果列表中

代码

public class Solution {
    
    List res;
    
    public List letterCombinations(String digits) {
        // 建立映射表
        String[] table = {" ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        StringBuilder tmp = new StringBuilder();
        res = new LinkedList();
        helper(table, 0, tmp, digits);
        return res;
    }
    
    private void helper(String[] table, int idx, StringBuilder tmp, String digits){
        if(idx == digits.length()){
            // 找到一种结果，加入列表中
            if(tmp.length()!=0) res.add(tmp.toString());
        } else {
            // 找出当前位数字对应可能的字母
            String candidates = table[digits.charAt(idx) - "0"];
            // 对每个可能字母进行搜索
            for(int i = 0; i < candidates.length(); i++){
                tmp.append(candidates.charAt(i));
                helper(table, idx+1, tmp, digits);
                tmp.deleteCharAt(tmp.length()-1);
            }
        }
    }
}

GPU云服务器云服务器 Combinations Letter LeetCode automation of com

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

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

leetcode17 Letter Combinations of a Phone Number

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

snowell 2019-08-14 18:09 评论0 收藏0
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
九宫格键盘输入

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

Xufc 2019-07-25 12:04 评论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