题目描述

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

示例：
输入：digits = “23”
输出：[“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]

题目分析

DFS，每层处理一个按键

Java

private List<List<Character>> data = new ArrayList<>();
private List<String> ans = new ArrayList<>();
private List<Character> list = new ArrayList<>();

public List<String> letterCombinations(String digits) {
    data.add(new ArrayList<>());
    data.add(new ArrayList<>());
    data.add(Arrays.asList('a', 'b', 'c'));
    data.add(Arrays.asList('d', 'e', 'f'));
    data.add(Arrays.asList('g', 'h', 'i'));
    data.add(Arrays.asList('j', 'k', 'l'));
    data.add(Arrays.asList('m', 'n', 'o'));
    data.add(Arrays.asList('p', 'q', 'r', 's'));
    data.add(Arrays.asList('t', 'u', 'v'));
    data.add(Arrays.asList('w', 'x', 'y', 'z'));

    dfs(digits, 0);
    return ans;
}

private void dfs(String digits, int index) {
    if (index == digits.length()) {
        StringBuilder sb = new StringBuilder();
        for (Character ch : list) {
            sb.append(ch);
        }
        ans.add(sb.toString());
        return;
    }

    int num = digits.charAt(index) - '0';
    List<Character> keys = data.get(num);
    for (Character ch : keys) {
        list.add(ch);
        dfs(digits, index + 1);
        list.remove(list.size() - 1);
    }
}

Kotlin

private val map = arrayOf(
    listOf(),
    listOf(),
    listOf('a', 'b', 'c'),
    listOf('d', 'e', 'f'),
    listOf('g', 'h', 'i'),
    listOf('j', 'k', 'l'),
    listOf('m', 'n', 'o'),
    listOf('p', 'q', 'r', 's'),
    listOf('t', 'u', 'v'),
    listOf('w', 'x', 'y', 'z')
)
private val ans = ArrayList<String>()
private val list = ArrayList<Char>()

fun letterCombinations(digits: String): List<String> {
    dfs(digits, 0)
    return ans
}

private fun dfs(digits: String, index: Int) {
    if (index == digits.length) {
        val sb = StringBuilder()
        for (ch in list) {
            sb.append(ch)
        }
        ans.add(sb.toString())
        return
    }
    val num = digits[index] - '0'
    val chs = map[num] ?: return
    for (ch in chs) {
        list.add(ch)
        dfs(digits, index + 1)
        list.removeLast()
    }
}