LeetCode 17. 电话号码的字母组合 java 计算键盘组合字母 给定参数输出键盘字母组合 求键盘字母组合

给定一个仅包含数字 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'] 的一个数字。

来源力扣LeetCode
链接https://leetcode.cn/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。

了解回溯算法递归

首先使用哈希表存储每个数字对应的所有可能的字母然后进行回溯操作。

回溯过程中维护一个字符串表示已有的字母排列如果未遍历完电话号码的所有数字则已有的字母排列是不完整的。该字符串初始为空。每次取电话号码的一位数字从哈希表中获得该数字对应的所有可能的字母并将其中的一个字母插入到已有的字母排列后面然后继续处理电话号码的后一位数字直到处理完电话号码中的所有数字即得到一个完整的字母排列。然后进行回退操作遍历其余的字母排列。

回溯算法用于寻找所有的可行解如果发现一个解不可行则会舍弃不可行的解。在这道题中由于每个数字对应的每个字母都可能进入字母组合因此不存在不可行的解直接穷举所有的解即可。

leetCode给出的复杂度分析

 

回溯模板

function backtrack(n, used) {
    // 判断输入或者状态是否非法
    if (input/state is invalid) {
        return;
  	}
    // 判读递归是否应当结束满足结束条件就返回结果
    if (match condition) {
        return some value;
  	}
    // 遍历当前所有可能出现的情况并尝试每一种情况
    for (all possible cases) {
        // 如果上一步尝试会影响下一步尝试需要写入状态
        used.push(case)
        // 递归进行下一步尝试搜索该子树
        result = backtrack(n + 1, used)
        // 在这种情况下已经尝试完毕重置状态以便于下面的回溯尝试
        used.pop(case)
    } 
}

递归代码

package com.shoujinshang.api.controller;

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

/**
 * beyond your self and trust your self.
 *
 * @Author: lbc
 * @Date: 2023-02-07 13:02
 * @email: 594599620@qq.com
 * @Description: oh my god niu bi...
 */
public class Solution {

    // 数字到号码的映射 前面两个为 键盘 0, 1对应的字母值
    private static String[] map = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    // 路径
    private static StringBuilder sb = new StringBuilder();

    // 结果集
    private static List<String> res = new ArrayList<>();

    public static List<String> letterCombinations(String digits) {
        if (digits == null || digits.length() == 0) {
            return res;
        }
        backtrack(digits, 0);
        return res;
    }

    /**
     * 回溯函数
     *
     * @param digits
     * @param index
     */
    private static void backtrack(String digits, int index) {
        if (sb.length() == digits.length()) {
            res.add(sb.toString());
            return;
        }

        // char 转int 参数-'0'即可
        String val = map[digits.charAt(index) - '0'];
        for (char ch : val.toCharArray()) {
            sb.append(ch);
            backtrack(digits, index + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }

    public static void main(String[] args) {
        List<String> strings = letterCombinations("27");
        System.out.println(strings.toString());
    }

}