题目描述
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
示例 1：
1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]
示例 2：
1
2
输入：digits = ""
输出：[]
示例 3：
1
2
输入：digits = "2"
输出：["a","b","c"]
Java Solution
/*
* @lc app=leetcode.cn id=17 lang=java
*
* [17] 电话号码的字母组合
*/
// @lc code=start
class Solution {
// 解题思路 用链表（先进先出）先拿出前面的数字，与下一个数字后组合完后再放回队列，当组合完的字符串长度与输入数字长度一样则返回链表
/*
* 输入23
* c -> b -> a poll a (与2的所有数组结合再add到队列)
* af -> ae -> ad -> c -> b poll b (与2的所有数组结合再add到队列)
* bf -> be -> bd -> af -> ae -> ad -> c poll c (与2的所有数组结合再add到队列)
* cf -> ce -> cd -> bf -> be -> bd -> af -> ae -> ad (peek 得到 ad的长度 与 12 长度一样则退出)
*/
public List<String> letterCombinations(String digits) {
LinkedList<String> resList = new LinkedList<>();
if(digits == null || digits.isEmpty()) {
return resList;
}
char[][] map = { {'a', 'b', 'c'}, {'d','e' ,'f'}, {'g', 'h', 'i'}, {'j', 'k', 'l'}, {'m', 'n', 'o'}, {'p', 'q', 'r', 's'}, {'t', 'u', 'v'}, {'w', 'x', 'y', 'z'} };
resList.add("");
while(resList.peek().length() < digits.length()) {
String pre = resList.poll();
int nextIdx = pre.length();
int index = digits.charAt(nextIdx) - '2';
char[] addList = map[index];
for(char c : addList) {
resList.add(pre + c);
}
}
return resList;
}
}
// @lc code=end
