【Leetcode】17. 电话号码的字母组合(Letter Combinations of a Phone Number)

题目描述：

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

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

示例:

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

分析：

用递归就可以完成，但官方把他归进了回溯法，标题就写回溯法吧~

题目中要求给定包含2-9数字的长度为N的字符串，每个数字对应几个字母，求这些所有字母的组合，如图所示。

我们可以用Map的key存储数字2-9，用value存储这个数字对应的字母（例如，2对应abc）。

递归可以很好的解决这个问题，首先从字符串的index=0开始进入，根据Map上该key对应的value值（例如key=2，value="abc"），分别取这些字母，并进入到下一个过程中。

用Map存储的过程如下：

 Map<String, String> map = new HashMap<String, String>() {{

    put("2", "abc");

    put("3", "def");

    put("4", "ghi");

    put("5", "jkl");

    put("6", "mno");

    put("7", "pqrs");

    put("8", "tuv");

    put("9", "wxyz");

  }};

可以看到，答案需要一个List<String>作为返回，我们则可以：

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

接下来到了写函数，我们创建一个名为dfs的函数：

public void dfs(String digits, int step, String answer) {

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

            ans.add(answer);

            return;

        }

        char c = digits.charAt(step);

        String value = map.get(c +"");

        for (int i = 0; i < value.length(); i++) {

            dfs(digits, step + 1, answer + value.charAt(i));

        }

    }

整合一下，最后AC代码为：

class Solution {

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

    Map<String, String> map = new HashMap<String, String>() {{

            put("2", "abc");

            put("3", "def");

            put("4", "ghi");

            put("5", "jkl");

            put("6", "mno");

            put("7", "pqrs");

            put("8", "tuv");

            put("9", "wxyz");

          }};

    public List<String> letterCombinations(String digits) {

        if (digits.length() == 0 || digits == null)

            return ans;

        dfs(digits, 0, "");

        return ans;

    }

    public void dfs(String digits, int step, String answer) {

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

            ans.add(answer);

            return;

        }

        char c = digits.charAt(step);

        String value = map.get(c + "");

        for (int i = 0; i < value.length(); i++) {

            dfs(digits, step + 1, answer + value.charAt(i));

        }

    }

}

巴特西

Leetcode之回溯法专题-17. 电话号码的字母组合(Letter Combinations of a Phone Number)

【Leetcode】17. 电话号码的字母组合(Letter Combinations of a Phone Number)

最新文章

热门文章