【题目】

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.

【分析】

无

【代码】

/*********************************
*   日期：2015-01-22
*   作者：SJF0115
*   题目: 17.Letter Combinations of a Phone Number
*   网址：https://oj.leetcode.com/problems/letter-combinations-of-a-phone-number/
*   结果：AC
*   来源：LeetCode
*   博客：
**********************************/
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> vec;
        if(digits.length() <= 0){
            vec.push_back(digits);
            return vec;
        }//if
        vector<char> number;
        DFS(vec,digits,number);
        return vec;
    }
private:
    void DFS(vector<string> &vec,string digits,vector<char> &number){
        string letters[] = {" ","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        // 一种组合完成
        int curLen = number.size();
        if(curLen == digits.length()){
            string letter;
            for(int i = 0;i < curLen;++i){
                letter += number[i];
            }//for
            vec.push_back(letter);
            return;
        }//if
        // 数字
        int num = digits[curLen] - '0';
        // 数字所对应的字母长度
        int len = letters[num].length();
        for(int i = 0;i < len;++i){
            number.push_back(letters[num][i]);
            DFS(vec,digits,number);
            number.pop_back();
        }//for
    }
};

int main(){
    Solution solution;
    string number = "2";
    vector<string> result = solution.letterCombinations(number);
    // 输出
    for(int i = 0;i < result.size();++i){
        cout<<result[i]<<endl;
    }//for
    return 0;
}

【代码二】

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        DFS(digits,0,"",result);
        return result;
    }
private:
    void DFS(string digits,int cur,string path,vector<string> &result){
        string keyboard[] = {" ","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        if(cur == digits.length()){
            result.push_back(path);
            return;
        }//if
        int len = keyboard[digits[cur] - '0'].length();
        for(int i = 0;i < len;++i){
            char c = keyboard[digits[cur] - '0'][i];
            DFS(digits,cur + 1,path + c,result);
        }//for
    }
};

注意一种特殊情况：