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 in lexicographical order, your answer could be in any order you want.
A:
-----------------------3 rd ------递归调用------- 作者-对于digits=""的情况跟我们假设的不一样------------最新版本的改了。------
public class Solution { public List<String> letterCombinations(String digits) { // assume all chars in digits are in 2 to 9 List<String> list = new LinkedList<String>(); if(digits.length() == 0) { list.add(""); return list; } HashMap<Character,String> map = new HashMap<Character,String>(); map.put('2',"abc"); map.put('3',"def"); map.put('4',"ghi"); map.put('5',"jkl"); map.put('6',"mno"); map.put('7',"pqrs"); map.put('8',"tuv"); map.put('9',"wxyz"); return helper(map,digits); } public List<String> helper(HashMap<Character, String> map, String digits){ List<String> list = new LinkedList<String>(); String str = map.get(digits.charAt(0)); if(digits.length() == 1){ for(int i =0;i<str.length();i++) list.add(""+str.charAt(i)); }else{ List<String> newList = helper(map, digits.substring(1)); for(int i =0;i<str.length();i++) for(String tmp:newList) list.add(str.charAt(i)+tmp); } return list; } }
--------见最后面----
Mistakes:
1: 将al,加入到all中的时候, 没有考虑当all为空的时候。 导致all一直为空。
2: given input as "", we expect the value [""] , 这个,好像是因为, 作者的实现方法和我们的不一样,因此,我们这里,需要多处理一下。 呵呵 ------------ 以后问明白了。 这种边边角角的情况。
--------------------------------2 nd Pass-------------------------
Mistakes:
1: 这里,应该算是题意给的不太对。
public class Solution { public List<String> letterCombinations(String digits) { Map<Character, String> map = new HashMap<>(); map.put('2',"abc"); map.put('3',"def"); map.put('4',"ghi"); map.put('5',"jkl"); map.put('6',"mno"); map.put('7',"pqrs"); map.put('8',"tuv"); map.put('9',"wxyz"); List<String> res = new LinkedList(); if(digits.length()==0) return res; res.add("");// this is the base case for 0 length for(int i =0;i<digits.length();i++){ List<String> res2 = new LinkedList(); String str = map.get(digits.charAt(i)); for(String ss : res) for(char ch : str.toCharArray()) res2.add(ss+ch); res = res2; } return res; } }
No comments:
Post a Comment