[LeetCode] 17. Letter Combinations of a Phone Number

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:
Input: digits = “23”
Output: [“ad”,”ae”,”af”,”bd”,”be”,”bf”,”cd”,”ce”,”cf”]

Example 2:
Input: digits = “”
Output: []

Example 3:
Input: digits = “2”
Output: [“a”,”b”,”c”]

Constraints:
0 <= digits.length <= 4
digits[i] is a digit in the range [‘2’, ‘9’].

电话号码的字母组合。

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路一 - backtracking

题意是给一个 string，里面是数字，请返回所有可能的字母组合。这是典型的 backtracking 回溯类的题目，一定要会。回溯类的题目一般都是带着一个 prefix 前缀，然后不断地尝试不同的组合直到最后的结果满足一定的情况，往往是长度满足情况。这道题有两种解法，其中第二种解法也是一定会考的。

第一种解法是典型的回溯解法，会用到一个 helper 函数。递归函数的跳出条件就是遍历完了当前所有的数字。每当遍历一个数字的时候，拿出它背后所有的字母，比如 2，就拿出 abc 来分别往结果集里面添加。

复杂度

时间O(4^n * n) - 每个按键平均对应 4 个字母，那么递归次数为一个满四叉树的节点个数。每把一个结果加入结果集的时候，需要 new 一个新的 string 所以还需要再乘以 n
空间O(4^n) - output list

代码

Java实现一

class Solution {
	private String[] mapping = new String[] { "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

	public List<String> letterCombinations(String digits) {
		List<String> res = new ArrayList<>();
		// corner case
		if (digits == null || digits.length() == 0) {
			return res;
		}
		helper(res, digits, "", 0);
		return res;
	}

	public void helper(List<String> res, String digits, String prefix, int index) {
		// base case
		if (index == digits.length()) {
			res.add(prefix);
			return;
		}
		// 拿出每个数字背后对应的字母们
		String letters = mapping[digits.charAt(index) - '0'];
		for (char c : letters.toCharArray()) {
            helper(res, digits, prefix + c, index + 1);
        }
	}
}

我再提供一个 StringBuilder 的代码，注意代码中是有撤回操作的。String 的版本为什么不需要撤回是因为进入下一层递归的时候 String 创建了新的对象。
Java实现二

class Solution {
    String[] mapping = new String[] {"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    public List<String> letterCombinations(String digits) {
        List<String> res = new ArrayList<>();
        // corner case
        if (digits == null || digits.length() == 0) {
            return res;
        }
        helper(res, new StringBuilder(), digits, 0);
        return res;
    }

    private void helper(List<String> res, StringBuilder sb, String digits, int index) {
        if (index == digits.length()) {
            res.add(sb.toString());
            return;
        }

        String letters = mapping[digits.charAt(index) - '0'];
        for (int i = 0; i < letters.length(); i++) {
            sb.append(letters.charAt(i));
            helper(res, sb, digits, index + 1);
            sb.deleteCharAt(sb.length() - 1);
        }
    }
}

思路二 - bfs

第二种做法是类似树的层序遍历。一开始将一个空的字符串加入一个用linkedlist创建的队列，接着遍历input，拿到每一个数字，加入队列，弹出的时候，遵循先进先出的原则，弹出某个字母，再根据长度判断是否需要再attach新的字符。动图链接。

复杂度

时间O(3^n)
空间O(3^n)

代码

Java实现

class Solution {
    public List<String> letterCombinations(String digits) {
        LinkedList<String> res = new LinkedList<>();
        if (digits == null || digits.length() == 0) {
            return res;
        }
        String[] mapping = new String[] { "0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        res.add("");
        for (int i = 0; i < digits.length(); i++) {
            int num = digits.charAt(i) - '0';
            while (res.peek().length() == i) {
                String t = res.remove();
                for (char s : mapping[num].toCharArray()) {
                    res.add(t + s);
                }
            }
        }
        return res;
    }
}