将其建模为 BFS 背后的直觉

Question

我正试图在 LeetCode.com 上解决这个问题：

Given a digit string, return all possible letter combinations that the number could represent. The mappings between the numbers and characters is like the telephone keypad. So:
2 <-> abc,
3 <-> def,
4 <-> ghi,
and so on...

Input: "23";
Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

高度赞成的解决方案如下：

class Solution {
public:
    vector<string> letterCombinations(string digits) {
        std::vector< string > vec;
        if(digits.length()==0)
            return vec;

        std::queue< std::string > ans;
        std::string mapping[]={"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

        ans.push("");
        for(int i=0; i<digits.length(); i++)
        {
            int x = (digits[i]-'0');
            while(ans.front().length()==i)
            {
                std::string t=ans.front();
                ans.pop();
                for(int j=0; j<mapping[x].length(); j++)
                {
                    ans.push(t+mapping[x][j]);
                }
            }
        }

        std::string val;
        int size=ans.size();
        for(int i=0; i<size; i++)
        {
            val=ans.front();
            ans.pop();
            vec.push_back(val);
        }
        return vec;
    }
};

我有以下问题：

将其建模为 BFS 问题背后的直觉是什么？按照 I 的想法，我会有两个向量，一个包含 a、b 和 c 作为元素（都映射到 2)，另一个持有 d、e 和 f 作为元素（全部映射到 3），然后简单地使用循环将元素组合为 ad,ae,等等。但这显然是低效的。那么 BFS 在这里如何应用和帮助呢？
究竟是怎么回事，在 while 循环的条件下 - ans.front().length()==i - 从逻辑上讲，为什么归纳变量 i 与队列中值的长度进行比较？

谢谢！

Answer 1

What is the intuition behind modeling this as a BFS

这不是真正的 BFS：作者没有充分理由使用队列 - 他们也可以使用两个向量 - 一个用于上一代字符串，一个用于当前一代。这将使他们不必检查队列前面的项目的长度，即 ans.front().length()==i：他们可以写 while (!priorGen.empty()) ...

What exactly is going on, in the condition in the while loop ...

该算法通过 "generations" 生成字符串，将新字符添加到先前 "generation."

的每个字符串的末尾

零代是单个空字符串
第 x 代是从第 x-1 代生成的，方法是在第 x-1

队列包含两代字符串 - 前一代和当前一代。当前一代的字符串比上一代的字符串长一个字符。循环条件确保循环继续，直到我们运行在上一代中用完字符串。

这里是修改后的代码，它使用两个单独的 "generation" 向量而不是单个队列，代码的其余部分保持不变：

vector<string> letterCombinations(string digits) {
    string mapping[]={"0", "1", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    vector<string> priorGen {""};
    vector<string> currentGen;
    if (!digits.size()) return currentGen;
    for(int i=0 ; i < digits.length() ; i++) {
        int x = (digits[i]-'0');
        while(!priorGen.empty()) {
            string t = priorGen.back();
            priorGen.pop_back();
            for(int j=0 ; j < mapping[x].length() ; j++) {
                currentGen.push_back(t+mapping[x][j]);
            }
        }
        swap(priorGen, currentGen);
    }
    return priorGen;
}

将其建模为 BFS 背后的直觉

Intuition behind modeling it as a BFS

c++

queue

breadth-first-search