LeetCode回溯算法组合问题——17.电话号码字母组合

导读:本篇文章讲解 LeetCode回溯算法组合问题——17.电话号码字母组合,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

一、题目描述:

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

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

LeetCode回溯算法组合问题——17.电话号码字母组合

 

二、分析

1.本题是一个经典的回溯算法题目,怎么辨别题解需要使用回溯算法呢? 

回溯法,一般可以解决如下几种问题:

  • 组合问题:N个数里面按一定规则找出k个数的集合
  • 切割问题:一个字符串按一定规则有几种切割方式
  • 子集问题:一个N个数的集合里有多少符合条件的子集
  • 排列问题:N个数按一定规则全排列,有几种排列方式
  • 棋盘问题:N皇后,解数独等等

2.回溯法模板

回溯三部曲:

(1)返回值以及参数

返回值一般为void。再来看一下参数,因为回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来,所以一般是先写逻辑,然后需要什么参数,就填什么参数

(2)回溯函数终止条件

什么时候达到了终止条件,一般来说搜到叶子节点了,也就找到了满足条件的一条答案,把这个答案存放起来,并结束本层递归

(3)回溯搜索的遍历过程。

for循环是横向遍历可以理解一个节点有多少个孩子,这个for循环就执行多少次

backtracking(递归)就是纵向遍历,这样就把这棵树全遍历完了,一般来说,搜索叶子节点就是找的其中一个结果了。

总结回溯算法模板如下:

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择:本层集合中元素(树中节点孩子的数量就是集合的大小)) {
        处理节点;
        backtracking(路径,选择列表); // 递归
        回溯,撤销处理结果
    }
}

3.代码

class Solution {
    List<String> list=new ArrayList<>();
    public List<String> letterCombinations(String digits) {
        if(digits==null||digits.length()==0){
            return list;
        }
      Map<Character, String> map = new HashMap<Character, 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");
        }};
        dfs(0,map,digits,new StringBuilder());
        return list;
    }

    public void dfs(int index,Map<Character, String> map,String digits,StringBuilder builder){
        if(index==digits.length()){
            list.add(builder.toString());
            return;
        }
        char num=digits.charAt(index);
        String s=map.get(num);
        for(int i=0;i<s.length();i++){
            builder.append(s.charAt(i));
            dfs(index+1,map,digits,builder);
            builder.deleteCharAt(index);
        }
    }
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由极客之家整理,本文链接:https://www.bmabk.com/index.php/post/116129.html

(0)
Java光头强的头像Java光头强

相关推荐

发表回复

登录后才能评论
极客之家——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!