【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 条评论
登录 后参与评论

相关文章

来自专栏赵俊的Java专栏

计算最大值

1313
来自专栏ACM算法日常

Find the nth digit(二分查找) - HDU 1597

...

862
来自专栏数据结构与算法

26:统计满足条件的4位数个数

26:统计满足条件的4位数个数 总时间限制: 1000ms 内存限制: 65536kB描述 给定若干个四位数,求出其中满足以下条件的数的个数:  个位数上的...

4134
来自专栏章鱼的慢慢技术路

浅谈main(),int main(),void main(),int main(void)四者之间的区别

1153
来自专栏数据结构与算法

06:整数奇偶排序

06:整数奇偶排序 查看 提交 统计 提问 总时间限制: 1000ms 内存限制: 65536kB描述 给定10个整数的序列,要求对其重新排序。排序要求: 1...

3216
来自专栏和蔼的张星的图像处理专栏

60. 搜索插入位置二分查找__细节

给定一个排序数组和一个目标值,如果在数组中找到目标值则返回索引。如果没有,返回到它将会被按顺序插入的位置。

1053
来自专栏数据结构与算法

3110 二叉堆练习3

3110 二叉堆练习3 时间限制: 3 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 给定N...

2825
来自专栏微信公众号:Java团长

Java泛型详解

定义了一个List类型的集合,先向其中加入了两个字符串类型的值,随后加入一个Integer类型的值。这是完全允许的,因为此时list默认的类型为Object类型...

832
来自专栏数据结构与算法

1191 数轴染色

1191 数轴染色 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 黄金 Gold 题目描述 Description 在一条数轴...

3659
来自专栏数据结构与算法

BZOJ2212: [Poi2011]Tree Rotations(线段树合并)

可以证明,对于\(m\)个仅有一个元素,权值范围在\([1, n]\)的线段树合并的复杂度为\(mlogn\)

652

扫码关注云+社区