首页 > 代码库 > 17. Letter Combinations of a Phone Number

17. Letter Combinations of a Phone Number

2024-10-30 03:57:02   212人阅读

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.

技术分享

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.

 

BFS:

技术分享 
 1 class Solution {
 2 public:
 3     vector<string> letterCombinations(string digits)
 4     {
 5         vector<string> vs = {"", "", "abc", "def","ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
 6         vector<string> result;
 7         result.push_back("");
 8         if(digits.empty()) return {};
 9         for (size_t i = 0; i < digits.size(); ++i) {
10             vector<string> qc;
11             string strtmp(vs[digits[i]-‘0‘]);
12             for (size_t j = 0; j < strtmp.size(); ++j) {
13                 for (size_t k = 0; k < result.size(); ++k) {
14                     qc.push_back(result[k] + strtmp[j]);
15                 }
16             }
17             result = qc;
18         }
19         return result;
20     }
21 };
View Code

2% 3ms

对于含有0和1的项,比如"123",程序运行结果不符合预期.但是却通过OJ,所以此题有待严谨.

 

BFS:

class Solution {
public:
    vector<string> letterCombinations(string digits)
    {
        vector<string> vs = {"", "", "abc", "def","ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };
        vector<string> result;
        result.push_back("");
        if(digits.empty()) return {};
        for (size_t i = 0; i < digits.size(); ++i) {
            vector<string> qc;
            string strtmp(vs[digits[i]-‘0‘]);
            for (size_t j = 0; j < strtmp.size(); ++j) {
                for (size_t k = 0; k < result.size(); ++k) {
                    qc.push_back(result[k] + strtmp[j]);
                }
            }
            result.swap(qc);//swap does not take memory copy 
        }
        return result;
    }
};

the swap method thought by  asbear

65.33% 0ms

 

backtrackiing:

技术分享 
 1 class Solution { //by luming.zhang.75(Creater) redace85(Modifier) 
 2 public:
 3     vector<string> letterCombinations(string digits) {
 4         vector<string> ret;
 5         if(0>=digits.size()) return ret;
 6     
 7         const string map[]={"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
 8         backTrackingFun(map,digits,"",ret);
 9     
10         return ret;
11     }
12     
13     void backTrackingFun(const string m[], const string &digits, string r, vector<string> &ret){
14         int c=r.size();
15         if(digits.size()==c){
16             ret.push_back(r);
17             return;
18         }
19     
20         auto str = m[digits.at(c)-48];
21         for(auto it=str.cbegin();it!=str.cend();++it){
22             r.push_back(*it);
23             backTrackingFun(m,digits,r,ret);
24             r.pop_back();
25         }
26     }
27 };
View Code

2% 3ms

17. Letter Combinations of a Phone Number


联系
我们