【LeetCode】17. Letter Combinations of a Phone Number

1. 题目描述

Given a string containing digits from 2-9 inclusive, 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. Note that 1 does not map to any letters.

电话表盘

Example:

Input: "23"
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

2. 题解

题目说给定一个包含“2-9”的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如电话表盘所示，其中1不对应任何字母。

1. 暴力循环

自己首先想到的解法是暴力循环。有多少数字就对应多少个循环，每个循环的取值情况如表盘内容。比如“23”，对应的伪代码应该是：

result = []
for i in ['a','b','c']:
  temp = ""
  temp += i
  for j in ['d','e','f']:
    temp += j
    result.append(temp)

但是这种方法适用性并不强，因为这种方法严重依赖于输入字符串的长度，而且循环次数也太多了！！！
对于这种情况，一种可行方式是使用递归。每一个循环就调用一次函数，这样就可以把循环解放出来，不用事先计算循环次数。

2. 回溯法

我们从空字符串开始，遍历到字符串的一个数字时，添加一个当前数字对应的字母列表的字母；然后遍历下一个数字。终止条件是字符串遍历完成。

这里，我们先使用一个列表将每个数字到字母的映射关系保存下来。最终代码如下：

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        if (digits.empty()) return {};
        //数字到字母的映射关系
        vector<string> maps = {"","","abc","def","ghi",
                              "jkl","mno","pqrs","tuv","wxyz"};
        vector<string> result;
        string temp = "";
        
        helper(digits, 0, maps, result, temp);
        
        return result;

    }
    private:
    void helper(string& digits, int idx, vector<string>&maps, vector<string>& result, string& temp){
        if (idx == digits.size()){//终止条件
            result.push_back(temp);
            return;
        }
        string str_in_phone = maps[digits[idx]-'0'];
        for (auto ch: str_in_phone){
            temp.push_back(ch);
            helper(digits, idx+1, maps, result, temp);//下一次循环
            temp.pop_back();
        }
    }
};

欢迎大家关注我的公众号