我想在LeetCode.com上解决这个问题:
给定一个数字字符串,返回该数字可能代表的所有可能的字母组合。数字和字符之间的映射就像电话键盘。所以: 2 < - > abc, 3 < - > def, 4 < - > ghi, 等等...
输入:“23”; 输出:[“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;
}
};
我有以下问题:
a
,b
和c
作为元素(全部映射到2
),另一个拿着d
,e
和f
作为元素(全部映射到3
)然后简单地使用循环将元素组合为ad
,ae
等。但这显然效率低下。那么BFS如何适用并在这里提供帮助?ans.front().length()==i
- 逻辑上,为什么归纳变量i
与队列中的值的长度进行比较?谢谢!
将此建模为BFS的直觉是什么?
这不是真正的BFS:作者使用队列是没有充分理由的 - 他们也可以使用两个向量 - 一个用于上一代字符串,一个用于当前一代。这将使他们不必检查队列前面的项目的长度,即ans.front().length()==i
:他们将编写while (!priorGen.empty()) ...
究竟是怎么回事,在while循环的条件下......
该算法通过“代”生成字符串,在前一代“生成”的每个字符串的末尾添加一个新字符。
x
是从生成x-1
生成的,通过在生成x-1
中将相应数字的可能表示之一附加到每个字符串的末尾队列包含两代的字符串 - 前一个和当前的一个。来自当前一代的字符串比前一代字符串长一个字符。循环条件确保循环继续,直到我们在前一代中用完字符串。
这是修改后的代码,它使用两个单独的“生成”向量而不是单个队列,代码的其余部分保持不变:
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;
}