本文共 2014 字,大约阅读时间需要 6 分钟。
要解决这个问题,我们需要生成所有可能的字母组合,这些组合是根据给定的数字字符串在电话键盘上逐个数字对应的字母生成的。我们将使用回溯法来解决这个问题。
我们将使用回溯法来探索所有可能的字母组合。具体步骤如下:
import java.util.ArrayList;import java.util.HashMap;import java.util.List;import java.util.Map;public class Solution { private MapdigitMap; private List resultList; { digitMap = new HashMap<>(); digitMap.put('2', "abc"); digitMap.put('3', "def"); digitMap.put('4', "ghi"); digitMap.put('5', "jkl"); digitMap.put('6', "mno"); digitMap.put('7', "pqrs"); digitMap.put('8', "tuv"); digitMap.put('9', "wxyz"); resultList = new ArrayList<>(); } public List letterCombinationsWithBacktrack(String digits) { if (digits == null || digits.length() == 0) { return resultList; } backtrack("", digits); return resultList; } private void backtrack(String current, String remainingDigits) { if (remainingDigits.isEmpty()) { if (current.isEmpty()) { resultList.add(""); } else { resultList.add(current); } return; } char currentChar = remainingDigits.charAt(0); String letters = digitMap.getOrDefault(currentChar, ""); for (char c : letters.toCharArray()) { String newCurrent = current + c; String nextDigits = remainingDigits.substring(1); backtrack(newCurrent, nextDigits); } }}
digitMap
,其中每个数字对应其在电话键盘上的字母组合。letterCombinationsWithBacktrack
:该函数接收输入的数字字符串,如果输入为null
或空字符串,则返回一个空的结果列表。backtrack
:该递归函数处理当前组合和剩余的数字字符串。每次处理当前数字的第一个字符,获取对应的字母,逐个将其添加到当前组合中,然后递归处理剩下的数字部分。如果剩余的数字为空,则将当前组合添加到结果列表中。这种方法确保了我们遍历了所有可能的字母组合,生成了所有符合输入数字字符串的组合。
转载地址:http://plazk.baihongyu.com/