Letter Combinations of a Phone Number（17）
Letter Combinations of a Phone Number
Given a digit string, return all possible letter combinations that the number could represent.
A mapping of digit to letters (just like on the telephone buttons) is given below.
Input:Digit string "23" Output: ["ad", "ae", "af", "bd", "be", "bf","cd", "ce", "cf"]. Note: Although the above answer is lexicographical order, your answer could be in any order you want.
思路： 经典的backtracking解法。用HashMap存储数字对应的字母。然后就像subsets 一样。 这种题型都要利用返回void的helper函数，然后判断在什么条件的时候加入result中，然后在循环里面加入，递归再删除。对于这道题目， 当新生成的string的长度和digits的长度一样的时候就加入result里面。 然后for循环可能的char, 就是每个数字对应的char[]里的元素。
注意几点： string需要删减的时候用StringBuilder. 学一下如何新建带初始值的array。
时间复杂度：假设总共有n个digit，每个digit可以代表k个字符，那么时间复杂度是O(k^n)，就是结果的数量,所以是O(3^n)
空间复杂度：O(n)
public class Solution { public List letterCombinations(String digits) { List result = new ArrayList(); if (digits == null || digits.length() == 0) { return result; } HashMap hash = new HashMap(); hash.put('0', new char[]{}); hash.put('1', new char[]{}); hash.put('2', new char[] { 'a', 'b', 'c' }); hash.put('3', new char[] { 'd', 'e', 'f' }); hash.put('4', new char[] { 'g', 'h', 'i' }); hash.put('5', new char[] { 'j', 'k', 'l' }); hash.put('6', new char[] { 'm', 'n', 'o' }); hash.put('7', new char[] { 'p', 'q', 'r', 's' }); hash.put('8', new char[] { 't', 'u', 'v'}); hash.put('9', new char[] { 'w', 'x', 'y', 'z' }); StringBuilder s = new StringBuilder(); helper(result, hash, s, digits,0); return result; } private void helper(List result, HashMap hash, StringBuilder s, String digits, int i ) { if (digits.length() == s.length()) { result.add(s.toString()); return; } for (char c : hash.get(digits.charAt(i)) ) { s.append(c); helper(result,hash,s, digits, i + 1); s.deleteCharAt(s.length() - 1); } }}关键字：产品经理
版权声明
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！
