MENU

LeetCode17. Letter Combinations of a Phone Number(递归 / 回溯)

2019 年 04 月 11 日 • 阅读: 1191 • LeetCode阅读设置

LeetCode17. Letter Combinations of a Phone Number(递归)

  • Medium
  • Accepted:368,431
  • Submissions:898,738

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.

img

Example:

Input: "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.


链接

https://leetcode.com/problems/letter-combinations-of-a-phone-number

题意

给定一个包含2到9的数字串,每个字母能代表一些字母,对应于电话按钮上的数字和字母,求数字串能表示的所有字母组合。输出顺序任意。

题解

就是一个组合问题,可以使用递归来处理。假设digits代表数字串,s(digits)为数字串能表示的字母串。那么s(digits) = letter(digits[0]) + s(digits[1...n-1])。

时间复杂度:$T(n) = T(n-1) + n$,为$O(n^2)​$。

代码

  • Runtime: 4 ms, faster than 100.00% of C++ online submissions for Letter Combinations of a Phone Number.
  • Memory Usage: 8.7 MB, less than 62.00% of C++ online submissions for Letter Combinations of a Phone Number.
class Solution {
private:
    vector <string> ans;
    const string letterMap[10] =
            {
                " ",  // 0
                "",   // 1
                "abc", // 2
                "def", // 3
                "ghi", // 4
                "jkl", // 5
                "mno", // 6
                "pqrs", // 7
                "tuv", // 8
                "wxyz" // 9
            };

    // s中保存了此时由digits[0...index-1]得到的一个字母字符串
    // 寻找和digits[index]匹配的字母,获得digits[0...index]翻译得到的解
    void solve(const string & digits, int index, const string & s)
    {
        if (index == digits.size()) // 保存结果
        {
            ans.push_back(s);
            return ;
        }
        char c = digits[index];
        string letters = letterMap[c - '0'];
        for (int i = 0; i < letters.size(); ++i)
            solve(digits, index + 1, s + letters[i]);
    }

public:
    vector<string> letterCombinations(string digits) {
        ans.clear();
        if (digits.empty())
            return ans;
        solve(digits, 0, "");
        return ans;
    }
};

The end.
2019年4月11日 星期四