使用 Java ArrayList 打印电话号码可能出现的所有单词
给你一个手机键盘，以及需要按下的按键，你的任务是打印按下这些数字可能出现的所有单词。
输入输出场景
让我们通过一个例子来进一步理解:
输入
str = "32"
输出
[gd, hd, id, ge, je, ie, gf, hf, if]
按 3 次可以组成的字符是 g、h、i，按 2 次可以组成的字符是 d、e、f。因此，所有单词都将是第一个字符属于 g、h、i，第二个字符属于 d、e、f 的组合。
要根据电话号码打印所有可能的单词，您可以使用递归方法生成与电话号码对应的所有可能的字母组合。
步骤/方法
在此示例中，我们定义了一个 phoneMap，将每个数字映射到对应字母的列表。我们还定义了一个 getWordsFromDigits 函数，该函数接受当前数字、正在构造的当前单词以及所有可能单词的列表。
getWordsFromDigits 函数首先检查是否没有更多数字需要处理。如果是，它将当前单词添加到所有可能单词的列表中并返回。否则，它会检索与第一位数字对应的字母，并为每个字母递归调用 getWordsFromDigits，传入剩余的数字和更新后的当前单词。
在主函数中，我们初始化电话号码和一个空的单词列表，并使用这些参数调用 getWordsFromDigits。最后，我们循环遍历所有可能的单词列表，并逐一打印出来。
示例
Here is a sample code:
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class PhoneDigitsConvertToWords {
//用于存储电话数字和字符的哈希表
private static Map<Character, List<Character>> phoneDigitMap = new HashMap<>();
static {
phoneDigitMap.put('2', Arrays.asList('a', 'b', 'c'));
phoneDigitMap.put('3', Arrays.asList('d', 'e', 'f'));
phoneDigitMap.put('4', Arrays.asList('g', 'h', 'i'));
phoneDigitMap.put('5', Arrays.asList('j', 'k', 'l'));
phoneDigitMap.put('6', Arrays.asList('m', 'n', 'o'));
phoneDigitMap.put('7', Arrays.asList('p', 'q', 'r', 's'));
phoneDigitMap.put('8', Arrays.asList('t', 'u', 'v'));
phoneDigitMap.put('9', Arrays.asList('w', 'x', 'y', 'z'));
}
//Driver method
public static void main(String[] args) {
String digitsStr = "23";
List<String> words = new ArrayList<>();
getWordsFromPhoneDigits(digitsStr, "", words);
for (String word : words) {
System.out.println(word);
}
}
//从输入的电话号码字符串中获取单词的方法
private static void getWordsFromPhoneDigits(String digitsStr, String currentWord, List<String> words) {
if (digitsStr.length() == 0) {
words.add(currentWord);
return;
}
char digit = digitsStr.charAt(0);
List<Character> letters = phoneDigitMap.get(digit);
for (Character letter : letters) {
getWordsFromPhoneDigits(digitsStr.substring(1), currentWord + letter, words);
}
}
}
输出
ad ae af bd be bf cd ce cf
时间和空间复杂度
该解决方案的时间复杂度为 O(3^N * 4^M)，其中 N 表示对应 3 个字母(2、3、4、5、6、8)的数字数量，M 表示对应 4 个字母(7、9)的数字数量。这是因为对应三个字母的每个数字都有三个可能的字母，而对应四个字母的每个数字都有四个可能的字母。因此，共有 3^N * 4^M 种可能的字母组合。
由于这是可能生成的单词数量上限，因此该解决方案的空间复杂度也为 O(3^N * 4^M)。在最坏的情况下，每个字母组合都会生成一个有效的单词，因此我们必须将每个单词存储在单词列表中。
