1.使用回溯法进行解决,先记录下每个数字对应的字母有哪些.使用一个HashMap进行记录(key为数字,value为字母) 2.注意传入的数字有可能有两个,也有可能有更多. 3.如果传入的数字长度是0,则直接返回空即可 对于传入的数字进行分解,先取第一个数字比如题目"23"中的2, 然后再得到2对应的字母组合 4.对字母组合中的每一个字符都进行遍历,然后再添加数字中的下一个数字,重复此操作 比如2中可以取(a,b,c,) 对于三个字符串“a”,“b”,“c”再分别取下一个数字进行操作. a和数字3,操作后是a(d,e,f,) b和数字3操作后是b(d,e,f) c和数字3操作后是c(d,e,f,)
Map<String,String> phone = new HashMap<String,String>(){{ put("2", "abc"); put("3", "def"); put("4", "ghi"); put("5", "jkl"); put("6", "mno"); put("7", "pqrs"); put("8", "tuv"); put("9", "wxyz"); }}; List<String> result = new ArrayList<String>(); public List<String> letterCombinations(String digits){ if(digits.length() != 0){ bachTrace("",digits); } return result; } /** * combination是当前的一种字符串,digits是下一个数字字符串 * 如果这个数字字符串为空,则当前字符串就算是一种情况 * 如果这个数字字符串不为空,则当前字符串加上这个数字首位对应的字母组成其他情况. * @param combination * @param nextDigits */ private void bachTrace(String combination,String nextDigits){ //先判断nextDigits是否为空 if(nextDigits.length() == 0){ result.add(combination); //添加当前字符串进入结果集种 }else{ //取出第一个位置的数字,得到它对应的字母,进行挨个拼接. String letters = phone.get(nextDigits.substring(0, 1)); for(int i = 0;i < letters.length();i++){ //拼接每一个字母,进行回溯 String letter = letters.substring(i, i+1); bachTrace(combination+letter,nextDigits.substring(1)); } } }