Letter Combinations of a Phone Number

描述

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.

Phone Keyboard

Figure: Phone Keyboard

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.

分析

无

递归

  1. // Letter Combinations of a Phone Number
  2. // 时间复杂度O(3^n)，空间复杂度O(n)
  3. class Solution {
  4. public:
  5.     const vector<string> keyboard { " ", "", "abc", "def", // '0','1','2',...
  6.             "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
  8.     vector<string> letterCombinations (const string &digits) {
  9.         vector<string> result;
  10.         if (digits.empty()) return result;
  11.         dfs(digits, 0, "", result);
  12.         return result;
  13.     }
  15.     void dfs(const string &digits, size_t cur, string path,
  16.             vector<string> &result) {
  17.         if (cur == digits.size()) {
  18.             result.push_back(path);
  19.             return;
  20.         }
  21.         for (auto c : keyboard[digits[cur] - '0']) {
  22.             dfs(digits, cur + 1, path + c, result);
  23.         }
  24.     }
  25. };

迭代

  1. // Letter Combinations of a Phone Number
  2. // 时间复杂度O(3^n)，空间复杂度O(1)
  3. class Solution {
  4. public:
  5.     const vector<string> keyboard { " ", "", "abc", "def", // '0','1','2',...
  6.             "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
  8.     vector<string> letterCombinations (const string &digits) {
  9.         if (digits.empty()) return vector<string>();
  10.         vector<string> result(1, "");
  11.         for (auto d : digits) {
  12.             const size_t n = result.size();
  13.             const size_t m = keyboard[d - '0'].size();
  15.             // resize to n * m
  16.             for (size_t i = 1; i < m; ++i) {
  17.                 for (size_t j = 0; j < n; ++j) {
  18.                     result.push_back(result[j]);
  19.                 }
  20.             }
  22.             for (size_t i = 0; i < result.size(); ++i) {
  23.                 result[i] = result[i] + keyboard[d - '0'][i/n];
  24.             }
  25.         }
  26.         return result;
  27.     }
  28. };

原文: https://soulmachine.gitbooks.io/algorithm-essentials/content/cpp/brute-force/letter-combinations-of-a-phone-number.html