建筑工地网站,网站域名与网站首页网址,广告设计公司业务员如何开发客户,江西省网站建设先进表彰Problem: 17. 电话号码的字母组合 文章目录 题目描述思路解题方法复杂度Code 题目描述 思路
题目给定一串数字#xff0c;要求我们找出所有可能的字母组合#xff0c;即我们可以穷举出所有可能的结果#xff0c;而涉及到穷举我们自然可以想到利用回溯来解决问题#xff0c… Problem: 17. 电话号码的字母组合 文章目录 题目描述思路解题方法复杂度Code 题目描述 思路
题目给定一串数字要求我们找出所有可能的字母组合即我们可以穷举出所有可能的结果而涉及到穷举我们自然可以想到利用回溯来解决问题在本题目中我们选择给定字符串digits中的每一个字符作为决策阶段具体的 1.我们先创建一个哈希表将数字与其对应的字符存入数字作为键所有的字符作为值 2.编写并调用回溯函数当决策阶段等于digits的长度时将当前的决策路径添加到结果集合中否则从digits字符串的第一个字符开始回溯调用 解题方法 1.创建结果集合result若当digits为空时返回空集合 2.创建一个String类型的数组mappings作为哈希表索引从0-9用于存储数字与其字符的对应关系其中数字索引作为键所有的字符作为值 3.创建一个char类型的数组数组长度为digits字符串的长度作为回溯过程中的决策路径 4.编写并调用回溯函数参数列表为String[] mappings, String digits, int k, char[] path,其中由参数mappings 与digits决定参数列表k表示决策阶段path表示决策路径 4.1若k等于digits的长度时表示找到一个字母组合则将其添加到结果集合result中 4.2先得到当前决策阶段的digits中的数字字符再通过我们创建的哈希表mappins找出该数字字符对应的所有字母字符 4.3以当前的数字字符对应得所有字母字符开始遍历所有得字母字符并开始回溯调用 注意在上述解题方法中我们没有显示地在回溯调用后将当前的决策阶段状态还原回溯的本质就是一个多状态转移但这并不表示我们没有实现该操作而是因为我们定义的决策阶段是一个char类型的数组再回溯递归的调用过程中会将原来索引位置上的值给覆盖掉以达到恢复当前决策阶段的操作 复杂度
时间复杂度: 最坏时间复杂度 O ( 3 m × 4 n ) O(3^m \times 4^n) O(3m×4n),其中m表示选择对应只有三个字母的数字的个数n表示对应四个字母的个数 空间复杂度: O ( n m ) O(n m) O(nm) Code
class Solution {//Result listprivate ListString result new ArrayList();/*** Get the all possible combinations** param digits The combination given by topic* return ListString*/public ListString letterCombinations(String digits) {if (digits.length() 0) {return Collections.emptyList();}//Create the reflectionString[] mappings new String[10];mappings[2] abc;mappings[3] def;mappings[4] ghi;mappings[5] jkl;mappings[6] mno;mappings[7] pqrs;mappings[8] tuv;mappings[9] wxyz;//Decision pathchar[] path new char[digits.length()];backtrack(mappings, digits,0, path);return result;}/*** Use backtracking to find all possible combinations** param mappings Mapping between letters and numbers* param digits Combination of numbers given by topic* param k Decision stage* param path Decision path*/private void backtrack(String[] mappings, String digits, int k, char[] path) {//End conditionif (k digits.length()) {result.add(new String(path));return;}String mapping mappings[digits.charAt(k) - 0];for (int i 0; i mapping.length(); i) {path[k] mapping.charAt(i);backtrack(mappings, digits, k 1, path);}}
}
