17. 电话号码的字母组合

题目地址(17. 电话号码的字母组合)

https://leetcode-cn.com/problems/letter-combinations-of-a-phone-number/

题目描述

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
输入：digits = ""
输出：[]
示例 3：
输入：digits = "2"
输出：["a","b","c"]
提示：
0 <= digits.length <= 4
digits[i] 是范围 ['2', '9'] 的一个数字。

前置知识

123阿斯达

公司

• 暂无

思路

关键点

代码

• 语言支持：Java

Java Code:

class Solution {
        ArrayList<String> res = new ArrayList<>();
        public List<String> letterCombinations(String digits) {
            //判断输入字符是否为空
            if (digits == null || digits.length() == 0) {
                return res;
            }
            //将每种数字对应的字符写成一个字符串数组 前两个空对应0和1 1是没有字符的 剩下的是2-9
            String[] numString = {"","","abc","def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
            loop(digits , numString , 0);
            return res;
        }
        //避免频繁的字符串拼接 使用StringBuilder
        StringBuilder temp = new StringBuilder();
        //digits是给定的输入数字 例如23 , numString是数字对应的字母 num是当前取到第几个数了第一轮就是0
        void loop(String digits , String[]  numString ,int num){
            //终止条件给定的数字长度=当前循环到第几个数了
            if (digits.length() == num) {
                res.add(temp.toString());
                return;
            }
            //digits.charAt(num)取出第num个数 比如num为0 取出的是2 2是字符 -去'0'这个字符就是数字 也就是numString的第二个字符"abc"
            String str = numString[digits.charAt(num) - '0'];
            for (int i = 0; i < str.length(); i++) {
                //将str的第i个添加到StringBuilder中
                temp.append(str.charAt(i));
                //比如第一轮取a 然后往下递归一层就是def a与def进行拼接
                loop(digits, numString, num+1);
                //输出完了就把最后一个字符删除 继续下一次递归 回溯
                temp.deleteCharAt(temp.length()-1);
            }
        }
    }

复杂度分析

令 n 为数组长度。

• 时间复杂度：#card=math&code=O%28n%29&id=J9gqA)
• 空间复杂度：#card=math&code=O%28n%29&id=vFfa8)