题目
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
网络异常，图片无法展示
|
输入： digits = "23" 输出： ["ad","ae","af","bd","be","bf","cd","ce","cf"] 复制代码
分析
大家跟六六来分析下哈
- 第一个暴力解法
大家看哈，当digists="2"的时候，其实就是一个for循环就把结果写出来了，当我们digists="23"的时候，其实也就2个for循环，也就是双层for循环，但是我们发现，其实我们并不好写出来，因为我们并不知道到底有几层for循环，所以按这个思路，我们只能放弃
- 第二个，当然是我们的回溯了，那好，我们来看看这题如果我们要用回溯算法去解决的话，我们需要用什么样的思路，或者说，我们的步骤有几步的样子
- 第一个：就是我们要解决数字和字母如何映射
- 其中我们不能解决的多层for循环问题，我们就用回溯来解决
- 考虑一下边界条件，比如输入为null或者输入为"1"
题解
package com.six.finger.leetcode.five; /* 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 输入：digits = "23" 输出：["ad","ae","af","bd","be","bf","cd","ce","cf"] */ import java.util.*; import java.util.stream.Collectors; public class sixteen { public static void main(String[] args) { LinkedList<String> path = new LinkedList(); path.add("2"); path.add("3"); System.out.println(path.stream().collect(Collectors.joining("")).toString()); } public List<String> letterCombinations(String digits) { //判断临界条件 if (digits.length() == 0) { return new ArrayList<>(); } //首先 我们定义一个容器来装 数字和字母的映射关系 Map<Character, String> map = new HashMap(); map.put('1', ""); 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<>(); backtracking(res, new StringBuffer(), digits, map,0); return res; } private void backtracking(List<String> res, StringBuffer path, String digits, Map<Character, String> map,int index) { //结束条件 这边我们用一个stringbuffer来当作我们的path if (index==digits.length()){ res.add(path.toString()); return; } //从输入的diguts然后让他从1开始一个个去操作 char c = digits.charAt(index); String s = map.get(c); char[] chars = s.toCharArray(); for (char aChar : chars) { //加入的是第一个 path.append(aChar); backtracking(res,path,digits,map,index+1); //要按index去删除，删除的是最后一个哦 path.deleteCharAt(index); } } } 复制代码
其实我们来看看代码总结下
- 先找个容器存放数字和字母的映射，我这边用map
- 就是输入一个字符串，其实这个字符串每个字符都有index，所以我就从index=1开始去递归
- 然后我们用StringBuffer去存放走过的path，所以呢，我们要记回溯之后要删除这个path,需要用到deleteCharAt（index）,删除最后一个位置！
- 其他的好像也没啥了，按照回溯的模版去套
回溯模版
void backtracking(参数) { if (终止条件) { 存放结果; return; } for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) { 处理节点; backtracking(路径，选择列表); // 递归 回溯，撤销处理结果 } }
