好伤心 看了半年的一只猫被别人领养了# pets - 心有所宠
f*m
1 楼
给一个count and say的结果，确定有多少种可能的输入。比如，"1211" 可以解释成1
个2，1个1，121个1,12个11或者121个1。所以有四种可能的输入。
这个题是glassdoor上看到的，当时作者只是给了2，1个1，121个1这两个例子。
我有个backtracking的想法。
int numberOfWays(string& s, int index)
{
if (index == s.size())
return 1;
int num = 0;
for (int i = index; i < size(); ++i)
{
for (int j = i+1; j < size(); ++j)
{
if (s.substr(index, i) can be the count && s.substr(i+1, j) can
be the number)
num += numberOfWays(s, j+1);
}
}
return num;
}
不知道对不对，或者大家有没有更好的方法？
谢谢。
个2，1个1，121个1,12个11或者121个1。所以有四种可能的输入。
这个题是glassdoor上看到的，当时作者只是给了2，1个1，121个1这两个例子。
我有个backtracking的想法。
int numberOfWays(string& s, int index)
{
if (index == s.size())
return 1;
int num = 0;
for (int i = index; i < size(); ++i)
{
for (int j = i+1; j < size(); ++j)
{
if (s.substr(index, i) can be the count && s.substr(i+1, j) can
be the number)
num += numberOfWays(s, j+1);
}
}
return num;
}
不知道对不对，或者大家有没有更好的方法？
谢谢。
