[数据结构与算法] leetcode 17. Letter Combinations of a Phone Number（电话号码的字母组合）

开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> leetcode 17. Letter Combinations of a Phone Number（电话号码的字母组合） -> 正文阅读

[数据结构与算法]leetcode 17. Letter Combinations of a Phone Number（电话号码的字母组合）

在这里插入图片描述

电话号码按键上，每个数字对应着3到4个字母，
现给出几个数字，输出它们对应的字母的所有组合。

思路：
DFS
取出第1个数，找到它对应的字母，
然后按顺序取出字母，和下一个数字的所有字母组合，
当字母数和号码的长度相等时，把结果放进list。

注意有字母的号码是从2开始的。

class Solution {
    List<String> res = new ArrayList<>();
    int n = 0;
    String[] letters;
    
    public List<String> letterCombinations(String digits) {
        n = digits.length();
        if(n == 0) return res;
        
        StringBuilder sb = new StringBuilder();
        
        letters = new String[] {
            "abc", "def", "ghi", "jkl",
            "mno", "pqrs", "tuv", "wxyz"
        };
        
        dfs(0, digits, sb);
        
        return res;
    }
    
    void dfs(int id, String digits, StringBuilder sb) {
        if(sb.length() == n) {
            res.add(sb.toString());
            return;
        }
        String str = letters[digits.charAt(id) - '2'];
        
        for(int i = 0; i < str.length(); i++) {
            sb.append(str.charAt(i));
            
            dfs(id + 1, digits, sb);
            
            sb.deleteCharAt(sb.length() - 1);
            
        }
    }
}