17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

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

输入：digits = ""
输出：[]

解法一：回溯法

遍历所有可能的结果，返回成功的结果

List<String> res = new ArrayList<>(); HashMap<Character, String> hash = new HashMap<>(); public List<String> letterCombinations(String digits) { if (digits.length() == 0) return new ArrayList<>(); createHash(); letter(digits, 0, new StringBuilder()); return res; } void letter(String digits, int level, StringBuilder tempres) { if (level == digits.length()) { res.add(tempres.toString()); return; } String str = hash.get(digits.charAt(level)); for (int i = 0; i < str.length(); i++) { tempres.append(str.charAt(i)); letter(digits, level + 1, tempres); tempres.deleteCharAt(tempres.length() - 1); } } void createHash() { hash.put('2', "abc"); hash.put('3', "def"); hash.put('4', "ghi"); hash.put('5', "jkl"); hash.put('6', "mno"); hash.put('7', "pqrs"); hash.put('8', "tuv"); hash.put('9', "wxyz"); }

时间复杂度：O(3m×4n)

空间复杂度：O(m+n)

解法二：队列

HashMap<Character, String> hash = new HashMap<>(); public List<String> letterCombinations(String digits) { if(digits.length()==0) return new ArrayList<>(); createHash(); Deque<String> queue = new LinkedList<>(); queue.add(""); for (int i = 0; i < digits.length(); i++) { int size = queue.size(); for (int j = 0; j < size; j++) { String nowdigit = hash.get(digits.charAt(i)); String curqueue = queue.poll(); for (int k = 0; k < nowdigit.length(); k++) queue.add(curqueue + nowdigit.charAt(k)); } } List<String> res = new ArrayList<>(); int len = queue.size(); for (int i = 0; i < len; i++) res.add(queue.poll()); return res; } void createHash() { hash.put('2', "abc"); hash.put('3', "def"); hash.put('4', "ghi"); hash.put('5', "jkl"); hash.put('6', "mno"); hash.put('7', "pqrs"); hash.put('8', "tuv"); hash.put('9', "wxyz"); }

总结：心里要有层次遍历的树的结构

网址：17. 电话号码的字母组合 http://c.mxgxt.com/news/view/708974

相关内容

夫妻密码组合数字解读
怎么报名我是大明星，电话号码是多少
数字能量学手机号码：四吉星组合与人际关系
数字能量手机号之让你感情甜蜜贵人多多的手机号 哪个磁场组合容易有偏财
如何了解邵逸夫医院试管婴儿的电话号码？
电话号码遭泄露 龙梅子公司遭遇索赔门
七阿姨为涨人气自曝电话号码，粉丝赶忙拨打后，却直接坐不住了
字母哥就是笑话？几千块钱的股票天天打电话给管理人！管理人接你电话是人情！我们是在
足球明星球衣号码排名(足球明星球员球衣的号码和名字)
手机号码解析：数字能量学中八大磁场的优缺点。

随便看看