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

2019-08-07

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

【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)

原文地址:https://www.cnblogs.com/qinyuguan/p/11317054.html