萤火小屋

优律的知识库

  • 首页
  • 归档
  • 分类
  • 标签
  • 留言
  • 关于

  • 搜索
消息队列 RabbitMQ Redis 双指针 力扣 动态代理 Git YAML SpringBoot SpringMVC 回溯算法 分治算法 归并排序 快排 手撕 事务 MySQL索引 MySQL 小技巧 Spring Framework Spring 动态规划 Linux Android 贪心算法 操作系统 进程调度模拟 IPv6 数据库 计算机组成原理 计算机基础 栈 Java 静态路由 路由器 交换机 数字通信 网络工程 计算机网络 Web http 大学学习技巧 程序设计 算法

力扣17题-电话号码的字母组合-回溯算法题解

发表于 2021-04-11 | 分类于 力扣刷题 | 0 | 阅读次数 257

题目描述

给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

Mobile phone keyboard - force button 17

样例

  1. 示例 1:
    输入:digits = "23"
    输出:["ad","ae","af","bd","be","bf","cd","ce","cf"]

  2. 示例 2:
    输入:digits = ""
    输出:[]

  3. 示例 3:
    输入:digits = "2"
    输出:["a","b","c"]

  • 提示
    0 <= digits.length <= 4
    digits[i] 是范围 ['2', '9'] 的一个数字。

题目评估

知识点:DFS、递归、字符串、回溯算法
难度:中等

分析

本题实质是一个枚举组合的题目,只要是枚举组合就可以用回溯来递归一边求解,此时就可以用一个n叉树来表示枚举过程。(下图以样例1来做示范)

Recursive tree of backtracking algorithm

Java代码题解

//import java.util.ArrayList;
//import java.util.List;

class Solution {

    // 按键,注意索引和数字差2
    String[] mapper = {"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    List<String> res = null;  // 答案
    
    public List<String> letterCombinations(String digits) {
        res = new ArrayList<String>();
        
        if (digits == null || digits.length() == 0) {  // 空直接返回空
            return res;
        }

        char[] numbers = digits.toCharArray();  // 把字符串转换成字符数组
        char[] letters = digits.toCharArray();  // 这个数组用来放字母
        backtracking(numbers, letters, 0);      // 回溯

        return res;

    }

    public void backtracking(char[] numbers, char[] letters, int pointer){
        
        // pointer其实就是递归树的层数
        // 有几个数字递归树就有几层,如果pointer大于数字个数,就说明递归到叶子了
        if (pointer > numbers.length - 1) {
            res.add(new String(letters));
            return;
        }

        int num = (int)numbers[pointer] - 48;  // 把数字字符转换成整型数字

        for (int i = 0; i < mapper[num - 2].length(); i++) {  // 把按键num上的字母遍历一边
        	letters[pointer] = mapper[num - 2].charAt(i);  // 把遍历的字母装入letters数组中
            
            backtracking(numbers, letters, pointer + 1);  // 递归,此时pointer+1,处理下一层
        }

    }
}
力扣17题

复杂度分析

设m为3个字母的按键个数,n为4个字母的按键个数。
组合个数为3^m * 4^n,所以时间复杂度:O(3^m * 4^n)
递归需要占用栈空间,占用空间大小取决于递归树的层数,数字的个数就是递归树的层数,所以空间复杂度:O(n+m)

# 算法 # 程序设计 # 回溯算法
MySQL的数据类型
力扣1143题-最长公共子序列-题解
  • 文章目录
  • 站点概览
优律

优律

优律的知识库

77 日志
20 分类
44 标签
E-mail Twitter Instagram
Links
  • CZLisyx - 浮生志
  • Vedfolnir
0%
© 2019 — 2023 萤火小屋——优律的博客网站
网站已勉强运行 
Halo博客系统技术支持