CPP 简洁好写 广搜+深搜代码

广搜

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        vector<string> hash = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
        queue<string> q;
        if(!digits.size()) // 特判下返回空数组的情况
            return {};

        // 初始元素入队
        q.push("");

        // bfs
        for(int i = 0; i < digits.size(); i ++){
            int len = q.size(); // 用广搜去搜路径，需要记录当前队列的长度，确保每个元素都出过队
            while(len --){
                for(auto t: hash[digits[i]-'0']){
                    auto s = q.front();
                    s.push_back(t);
                    q.push(s);
                }
                q.pop();
            }
        }

        // 照顾输出格式，将队列元素转移到vector中
        vector<string> ans;
        while(!q.empty()){
            auto t = q.front();
            ans.push_back(t);
            q.pop();
        }

        return ans;     
    }
};

深搜

class Solution {
public:
    vector<string> hash = {"", "", "abc","def",
                           "ghi", "jkl", "mno",
                           "pqrs", "tuv", "wxyz"};
    vector<string> ans;
    vector<string> letterCombinations(string digits) {
        if(digits.size() == 0) return ans;
        dfs(digits, 0, "");
        return ans;
    }

    void dfs(string& digits, int u, string path){

        if(u == digits.size()){
            ans.push_back(path);
            return;
        }
        for(auto t: hash[digits[u]-'0']){
            dfs(digits, u+1, path+t);
        }
    }
};