17. Letter Combinations of a Phone Number（根据手机按键求字母的组合）

末蓝、 2022-06-08 07:30 39阅读 0赞

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.

![200px-Telephone-keypad2.svg.png][]

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.

**题目大意：**给定一个由数字构成的字符串，根据如图所示的手机按键中的 数字->字符串 的关系，求出所有可能字母的组合。例如，给定数字字符串 “23”，因为2在手机按键上对应字符串 “abc”，3在手机按键上对应字符串 “def”，所以输出由9个字符串组成，分别是 "ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"。

**解题思路：**采用递归的思想，每次传递的参数分别是：输入的数字字符串digits，记录要返回字符串的集合res，当前遍历到digits的位置pos，当前得到的字符串curCombination。每次根据pos取得digits对应位置的数字，然后根据这个数字去字典里面查找手机按键上对应的字符串，对字符串中的每个字符，添加到curCombination的末尾，并做下一层递归。当pos>=digits.length()时，已经遍历完digits，当前的curCombination就是一个满足条件的字符串，将其添加到res并return。

**解题代码：**（3ms，beats 78.36%）

class Solution {
        String[] dict = new String[] { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
    
    	public void letterCombination(String digits, List<String> res, int pos, String curCombination) {
    		if (pos >= digits.length()) {
    			res.add(curCombination);
    			return;
    		}
    		for (char c : dict[digits.charAt(pos) - '0'].toCharArray()) {
    			letterCombination(digits, res, pos + 1, curCombination + c);
    		}
    	}
    
    	public List<String> letterCombinations(String digits) {
    		if (digits == null || digits.length() == 0) {
    			return Collections.emptyList();
    		}
    		List<String> res = new ArrayList<>();
    		letterCombination(digits, res, 0, "");
    		return res;
    	}
    }

[200px-Telephone-keypad2.svg.png]: https://upload.wikimedia.org/wikipedia/commons/thumb/7/73/Telephone-keypad2.svg/200px-Telephone-keypad2.svg.png