Leetcode每日一题——17.电话号码的字母组合(回溯)

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

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

示例: 输入： 输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明：尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

这还是经典的回溯问题，回溯问题可以抽象成树模型来处理。比如"23"。

如上图（摘自《代码随想录》）

既然是回溯问题，那还是可以套用递归四部曲

class Solution {
    List<String> result = null;
	List<Character> path = null;
	String[] elements = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    	void letterCombinations1(int[] nums, int startIndex) {
		//递归作用：从nums中的startIndex开始取数字，取到长度符合条件后放在result里
		//参数：nums是字符串转化成的数字数组，startIndex表示这一层从nums的startIndex开始取数字
		//终止条件：path.length() == nums.length表示字符串中的数字被取完了，找到了一种组合
		//单层逻辑：从startIndex开始取数字中的字母，取完一位数字(每一位数字都对应着一个字符串，要把字符串当前索引取了才算这个数字取完)后取下一位。抽象成树结构就清楚了，数字字符串的长度相当于树的深度(也就是递归的深度)，每个数字对应的字母长度等于树的宽度。
		if(path.size() == nums.length) {//终止条件
			char[] temp = new char[path.size()];
			for(int i = 0; i < path.size(); i++)
				temp[i] = path.get(i);
			result.add(new String(temp));
			return;
		}
		for(int i = 0; i < elements[nums[startIndex]].length(); i++) {//从startIndex开始取数字中的字母
			path.add(elements[nums[startIndex]].charAt(i));
			letterCombinations1(nums, startIndex + 1);
			path.remove(path.size() - 1);//回溯，定义取数前的状态为这一层的初始状态，操作完初始化path，也就是回溯
		}
	}
	
	public List<String> letterCombinations(String digits) {
		result = new ArrayList<>();
		path = new ArrayList<>();
		if(digits.length() == 0) return result;
		int[] nums = new int[digits.length()];
		for(int i = 0; i < digits.length(); i++)//将字符串转化为数字数组方便哈希
			nums[i] = digits.charAt(i) - 0;
		letterCombinations1(nums, 0);
		return result;
    }
}

回溯记得再操作完后进行初始化哦，这是回溯算法的特点