说明：问题描述来源leetcode:

一、问题描述:

17. 电话号码的字母组合

难度中等2219

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：digits = "2"
输出：["a","b","c"]

提示：

• 0 <= digits.length <= 4
• digits[i] 是范围 ['2', '9'] 的一个数字。

通过次数609,617

提交次数1,052,457

二、题解：

题解1：

没剪枝

public class Solution {List result = new LinkedList<>();LinkedList path = new LinkedList<>();String digits;HashMap map = new HashMap<>();public Solution() {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");}public List letterCombinations(String digits) {this.digits = digits;if (digits.length() == 0) return result;backTracking(0);return result;}private void backTracking(int startIndex) {if (path.size() == digits.length()) result.add(getPathStr());for (int i = startIndex; i < digits.length(); i++) {char c = digits.charAt(i);for (char ch : map.get(c).toCharArray()) {path.add(ch);backTracking(i + 1);path.removeLast();}}}private String getPathStr() {StringBuilder stringBuilder = new StringBuilder();for (char c : path) {stringBuilder.append(c);}return stringBuilder.toString();}    
}

上面是没剪枝的，到底是怎么没剪枝呢？分析下，递归的最初那一层当遍历到digit第二个元素时，也就是最终的结果了，再进入递归是永远都不能满足path.size() == digits.length()，因此我们要剔除这些无用的递归操作，此时的path.size()肯定是小于startIndex的，这两者都不同步了。因此可以以startIndex != path.size()作为判断当前走入的递归是否是无意义的。

换一种处理数据的方法，并且进行剪枝：

class Solution {String[] strings = new String[8];List result = new LinkedList<>();LinkedList path = new LinkedList<>();String digits;public Solution() {strings[0] = "abc";strings[1] = "def";strings[2] = "ghi";strings[3] = "jkl";strings[4] = "mno";strings[5] = "pqrs";strings[6] = "tuv";strings[7] = "wxyz";}public List letterCombinations(String digits) {this.digits = digits;if (digits.length() == 0) return result;backTracking(0);return result;}private void backTracking(int startIndex) {if (startIndex != path.size()) return;//剪掉从digit第二个开始遍历后面的情况if (path.size() == digits.length()) result.add(getPathStr());for (int i = startIndex; i < digits.length(); i++) {int index = digits.charAt(i) - 50;for (char ch : strings[index].toCharArray()) {path.add(ch);backTracking(i + 1);path.removeLast();}}}private String getPathStr() {StringBuilder stringBuilder = new StringBuilder();for (char c : path) {stringBuilder.append(c);}return stringBuilder.toString();}
}

上面就缺什么呢？缺的是对数据的处理的优化，放进链表里还有提取出来，在一个一个地放StringBuilder里，再将StringBuilder转为String类型，如果一开始就是用StringBuilder这个容器来存储，而不是链表来存储不就省去取出链表元素的步骤了吗！

终极版：

public class Solution {String[] strings = new String[8];List result = new LinkedList<>();String digits;StringBuilder stringBuilder = new StringBuilder();public Solution() {strings[0] = "abc";strings[1] = "def";strings[2] = "ghi";strings[3] = "jkl";strings[4] = "mno";strings[5] = "pqrs";strings[6] = "tuv";strings[7] = "wxyz";}public List letterCombinations(String digits) {this.digits = digits;if (digits.length() == 0) return result;backTracking(0);return result;}private void backTracking(int startIndex) {if (startIndex != stringBuilder.length()) return;//剪掉从digit第二个开始遍历后面的情况if (stringBuilder.length() == digits.length()) result.add(stringBuilder.toString());for (int i = startIndex; i < digits.length(); i++) {int index = digits.charAt(i) - 50;for (char ch : strings[index].toCharArray()) {stringBuilder.append(ch);backTracking(i + 1);stringBuilder.deleteCharAt(stringBuilder.length() - 1);}}} 
}