LeetCode17-电话号码的字母组合

题目描述

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

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

示例 2：
输入：digits = “2”
输出：[“a”,”b”,”c”]

提示：

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

思路

开始想利用多层循环进行字符串拼接，效率先不考虑，由于给定的字符串长度不固定，所以无法使用 for 循环，while 循环应该也是不可以的。

假如给定字符串为 “23”，我们首先要得到数字 2 所在按键的字母 [a, b, c]，然后得到数字 3 所在按键的字母 [d, e, f]，然后进行循环拼接。假如给定字符串 “234” 呢？这时其实 “23” 可以拼接的字符串已经在上一步中有了，只需要再得到数字 3 所在按键的字母 [g, h, i]，然后与这几个字母进行拼接。

到这里其实思路已经出来了：给定长度为 n 的字符串，只需要将第 n 个数字所在按键的字母与前 n - 1 个数字所在按键的字母可以拼接成的字符串进行拼接。

代码实现

有史以来解答最快的一题，10 分钟写出代码，一次通过。

import java.util.ArrayList;  
import java.util.HashMap;  
import java.util.List;  
import java.util.Map;  
  
public class Solution17 {  
    public List<String> letterCombinations(String digits) {  
        Map<Character, List<String>> map = map();  
        List<String> strList = new ArrayList<>();  
        char[] digitsCharArray = digits.toCharArray();  
        for (char digit : digitsCharArray) {  
            List<String> chars = map.get(digit);  
            if (strList.isEmpty()) {  
                strList.addAll(chars);  
            } else {  
                List<String> tempStrList = new ArrayList<>();  
                for (String str : strList) {  
                    for (String c : chars) {  
                        tempStrList.add(str + c);  
                    }  
                }  
                strList = tempStrList;  
            }  
        }  
  
        return strList;  
    }  
  
    private static Map<Character, List<String>> map() {  
        Map<Character, List<String>> map = new HashMap<>();  
        map.put('2', List.of("a", "b", "c"));  
        map.put('3', List.of("d", "e", "f"));  
        map.put('4', List.of("g", "h", "i"));  
        map.put('5', List.of("j", "k", "l"));  
        map.put('6', List.of("m", "n", "o"));  
        map.put('7', List.of("p", "q", "r", "s"));  
        map.put('8', List.of("t", "u", "v"));  
        map.put('9', List.of("w", "x", "y", "z"));  
        return map;  
    }
}