【LeetCode】Letter Combinations of a Phone Number

【LeetCode】Letter Combinations of a Phone Number

题目

在手机九宫格键盘上输入一串数字,给出可能打印出来的字符串的集合。

分析

  • 先做一个map将数字映射到键盘上相应的字母集合。
  • 把按键顺序看成深度优先遍历的深度,每次dfs将深度d+1直到d=按键字符串的长度未知,此时即完成了一次按键可能的输出。

实现

    static Map<Integer, Character[]> map = new HashMap<Integer, Character[]>();   //数字键--键上的字母集合

    static {
        map.put(1, new Character[]{'\0'});
        map.put(2, new Character[]{'a', 'b', 'c'});
        map.put(3, new Character[]{'d', 'e', 'f'});
        map.put(4, new Character[]{'g', 'h', 'i'});
        map.put(5, new Character[]{'j', 'k', 'l'});
        map.put(6, new Character[]{'m', 'n', 'o'});
        map.put(7, new Character[]{'p', 'q', 'r', 's'});
        map.put(8, new Character[]{'t', 'u', 'v'});
        map.put(9, new Character[]{'w', 'x', 'y', 'z'});
        map.put(0, new Character[]{' '});

    }

    public List<String> letterCombinations(String digits) {
        ArrayList<String> result = new ArrayList<String>();
        if (digits == null || digits.length() == 0) return result;

        dfs(digits, 0, "", result);
        return result;
    }

    /**
     * 深度优先遍历,每次将数字键上的字母拼接到s中,一旦到达底部,则将s放入结果集中,并返回
     */
    private void dfs(String digits, int d, String s, ArrayList<String> result) {
        if (d == digits.length()) {
            result.add(s);
            return;
        }
        Integer number = Integer.parseInt(digits.charAt(d) + "");  //得到输入数字串在深度d时的数字

        for (Character c : map.get(number)) {                      //遍历该数字对应的每一个字母
            dfs(digits, d + 1, s + c, result);
        }
    }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习入门

LWC 62:743. Network Delay Time

LWC 62:743. Network Delay Time 传送门:743. Network Delay Time Problem: There are N...

2128
来自专栏Java Edge

网易17校招编程笔试题Java解法赏析(更新至第9题)1 合唱团(动态规划)编程实现 3Fibonacci数列4数字反转5下厨房67喜欢的数字8买苹果9

4536
来自专栏GIS讲堂

geotools中的空间关系(Geometry Relationships)和空间操作(Geometry Operations)

本文讲述geotools中的空间关系判断(Geometry Relationships)和空间操作(Geometry Operations)的编码实现。

773
来自专栏机器学习入门

LWC 52:686. Repeated String Match

LWC 52:686. Repeated String Match 传送门:686. Repeated String Match Problem: Given...

1865
来自专栏来自地球男人的部落格

[LeetCode] 39.Combination Sum

【原题】 Given a set of candidate numbers (C) (without duplicates) and a target ...

1917
来自专栏闵开慧

曾经做过的40道程序设计课后习题总结(三)

曾经做过的40道程序设计课后习题总结(三) 课后习题目录 1 斐波那契数列 2 判断素数 3 水仙花数 4 分解质因数 5 杨辉三角 6 学习成绩查询 7 求最...

3738
来自专栏向治洪

区块链的java实现

原文地址:http://java-lang-programming.com/en/articles/29 概述 MerkleTree被广泛的应用在比特币技术中,...

3549
来自专栏LeetCode

LeetCode 738. Monotone Increasing Digits

这是我开始选择的方法,非常直白,但是直白简单的方法往往不是最佳的解法,提交到LeetCode上,给我抛出一个超时,可见效率有多低。首先写一个函数,判断一个数是否...

660
来自专栏desperate633

LeetCode 77. Combinations题目分析代码

组给出两个整数n和k,返回从1......n中选出的k个数的组合。 样例 例如 n = 4 且 k = 2 返回的解为: [[2,4],[3,4],[2...

722
来自专栏LeetCode

LeetCode <heap>373. Find K Pairs with Smallest Sums

You are given two integer arrays nums1 and nums2 sorted in ascending order and a...

850

扫码关注云+社区