17. 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.

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:

class Solution { //by luming.zhang.75(Creater) redace85(Modifier) 
public:
    vector<string> letterCombinations(string digits) {
        vector<string> ret;
        if(0>=digits.size()) return ret;
    
        const string map[]={"0","1","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        backTrackingFun(map,digits,"",ret);
    
        return ret;
    }
    
    void backTrackingFun(const string m[], const string &digits, string r, vector<string> &ret){
        int c=r.size();
        if(digits.size()==c){
            ret.push_back(r);
            return;
        }
    
        auto str = m[digits.at(c)-48]; // '0' = 48
        for(auto it=str.cbegin();it!=str.cend();++it){
            r.push_back(*it);
            backTrackingFun(m,digits,r,ret);
            r.pop_back();
        }
    }
};

r size:0
a
a
r size:1
d
ad
r size:2
r pop back:d
e
ae
r size:2
r pop back:e
f
af
r size:2
r pop back:f
r pop back:a
b
b
r size:1
d
bd
r size:2
r pop back:d
e
be
r size:2
r pop back:e
f
bf
r size:2
r pop back:f
r pop back:b
c
c
r size:1
d
cd
r size:2
r pop back:d
e
ce
r size:2
r pop back:e
f
cf
r size:2
r pop back:f
r pop back:c
ad
ae
af
bd
be
bf
cd
ce
cf

2% 3ms