LeetCode17 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.(Medium)

分析：

很好的练习搜索的题目，可以用BFS和回溯法（DFS）两种方式来做一下练习。

自己写的时候没太想明白回溯的写法（参数，返回值等等），写的是BFS的解法，DFS参考的讨论区。

代码1：

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        string digMap[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
        vector<string> v;
        if (digits.size() == 0) {
            return v;
        }
        queue<string> q;
        for (int i = 0; i < digMap[digits[0] - '0'].size(); ++i) {
            q.push(string(1,digMap[digits[0] - '0'][i] ));
        }
        for (int i = 1; i < digits.size(); ++i) {
            int l = q.size();
            for (int j = 0; j < l; ++j) {
                string temp1 = q.front();
                q.pop();
                for (int k = 0; k < digMap[digits[i] - '0'].size(); ++k) {
                    string temp2 = temp1 + digMap[digits[i] - '0'][k];
                    q.push(temp2);
                }
            }
        }
        while (!q.empty()) {
            v.push_back(q.front());
            q.pop();
        }
        return v;
    }
};

回溯法：

class Solution {
private:
    string digMap[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
    void dfs(vector<string>& v, string& tempStr, int index, string& digits) {
        if (index == digits.size()) {
            v.push_back(tempStr);
            return;
        }
        for (int i = 0; i < digMap[digits[index] - '0'].size(); ++i) {
            //tempStr += digMap[digits[index] - '0'][i];
            tempStr.push_back(digMap[digits[index] - '0'][i]); //string的push_back和pop_back以前没用过
            dfs(v,tempStr,index + 1,digits);
            tempStr.pop_back();
        }
    }
public:
    vector<string> letterCombinations(string digits) {
        vector<string> result;
        if (digits.size() == 0) {
            return result;
        }
        string tempStr;
        dfs(result,tempStr,0,digits);
        return result;
    }
};