题解 | #牛名生成器#

知识点

深度优先搜索DFS / 宽度优先搜索BFS

思路说明

数据范围很小, 可以确定为可以用暴搜解决; 枚举每一位可以填的字母, 逐个字母向后填, 由于字母表table给出的字母顺序就是由小到大的, 逐个填入的结果一定是符合字典序小优先的

具体实现上可以用bfs或者dfs实现

AC Code (C++) BFS

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param digits string字符串 
     * @return string字符串vector
     */
    using psi = pair<string, int>;
    vector<string> letterCombinations(string digits) {
        // write code here
        unordered_map<char, string> table = {{'2', "abc"}, {'3', "def"}, {'4', "ghi"}, {'5', "jkl"}, {'6', "mno"}, {'7', "pqrs"}, {'8', "tuv"}, {'9', "wxyz"}};
        vector<string> res;
        // bfs
        queue<psi> q;
        q.emplace("", 0);
        int n = (int)digits.size();
        while (q.size()) {
            auto [s, idx] = q.front();
            q.pop();
            if (idx == n) {
                res.push_back(s);
                continue;
            }
            char cur = digits[idx];
            for (auto c : table[cur]) {
                s.push_back(c);
                q.emplace(s, idx + 1);
                s.pop_back();
            }
        }
        return res;
    }
};