题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例:

输入："23"

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

说明:

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

解题思路

回溯法

首先用一个数组把每个数字按键对应的字母存储起来，再把给定的字符串digits拆分成每一个单独的数字做处理。使用一个辅助函数进行处理

private void helper (String digits, int i,  StringBuilder cur, List<String> ans);

/*

String digits : 给定的数字组合字符串

int i ：当前（递归）处理的层数

StringBuilder cur ：当前字母组合

List<String> ans ：结果列表

*/

处理过程如下：

取出当前数字，以及该数字按键对应的字母，存为一个char数组curLetters
对curLetters进行遍历，将当前字符加入当前字母组合cur，然后（递归地）处理后一个数字
当层数等于给定字符串digits长度时，将当前字母组合cur加入结果列表ans，删除刚用过的字符（也就是当前字母组合的最后一个字母）
遍历完成后，结果列表ans就是题目要求的结果

Java 实现

private final static String[] digitsToChars =

        {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

public List<String> letterCombinations (String digits) {

    List<String> ans = new ArrayList<>();

    if (digits.length() == 0) return ans;

    helper(digits, 0, new StringBuilder(), ans);

    return ans;

}

private void helper (String digits, int i,  StringBuilder cur, List<String> ans) {

    if (digits.length() == i) {

        ans.add(cur.toString());

    } else {

        int digit = Character.getNumericValue(digits.charAt(i)); // 当前考察的数字

        char[] curLetters = digitsToChars[digit].toCharArray(); // 当前考察的数字对应的字母集合

        for (char c : curLetters) {

            cur.append(c);

            helper(digits, i + 1, cur, ans);

            cur.deleteCharAt(i); // 回溯：删掉刚才用过的字母

        }

    }

}

心得体会

刷探索卡片第一次遇到用回溯算法的题目，这一题中，回溯算法就体现在凑齐了digits.length()长度的字符串后，要往回删一个字符，方便进行新的字母组合。

巴特西

【LeetCode】17-电话号码的字母组合

题目描述

解题思路

回溯法

Java 实现

心得体会

最新文章

热门文章