让我们考虑一下祖玛游戏。假设我们在桌子上有一排球，这些球的颜色分别为红色(R)，黄色(Y)，蓝色(B)，绿色(G)和白色(W)。我们也有几个球。
现在，每次我们都可以从侧面选择一个球，然后将其插入行中。然后，如果有一组3个或以上相同颜色的球，则将其除去。继续这样做，直到无法取出更多球为止。
我们必须找到要插入的最小球，以删除桌子上的所有球。如果我们不能去除所有球，则返回-1。
因此，如果输入像“ WRRBBW”，而我们有“ RBW”，则答案将为3。我们可以在RR之后添加R，（WRR [R] BBW），删除后，序列将为(WBBW)，然后添加B，因此（WBB [B] W），删除后将为(WW)，然后添加W，因此序列将为（WW [W]）。这将删除所有球。
为了解决这个问题，我们将遵循以下步骤-
定义一个函数findMinStep()，这将花费s，
s：= s连接“#”
定义大小为26的数组v
对于初始化i：= 0，当i <手的大小，更新（将i增加1）时，执行-
将v [hand [i]-'A']增加1
ret：=调用函数solve(s,v)
返回ret> =如果INF不为零，则使用-1进行检查，否则使用ret
定义一个函数solve()，它将使用s，数组v，
如果s与“#”相同，则-
返回0
ret：= INF
对于初始化i：= 0，j：= 0，当j <s的大小时，更新（j增加1），-
v [x-'A'] = v [x-'A']-需要
ret：= ret的最小值，需要+ solve（s的子串从0到第i个索引）将s的子串从j串联到s的大小– j，v
v [x-'A'] = v [x-'A'] +需要
忽略以下部分，跳至下一个迭代
如果s [i]与s [j]相同，则-
需要：= 3-(j-i)
x：= s [i]
如果需要<= v [x-'A']，则-
i：= j
调用函数过程
如果s与“#”相同，则-
返回0
对于初始化i：= 0，j：= 0，当j <s的大小时，更新（j增加1），-
v [x-'A'] = v [x-'A']-需要
ret：= ret的最小值，需要+ solve（s的子串从0到第i个索引）将s的子串从j串联到s的大小– j，v
v [x-'A'] = v [x-'A'] +需要
忽略以下部分，跳至下一个迭代
如果s [i]与s [j]相同，则-
需要：= 3-(j-i)
x：= s [i]
如果需要<= v [x-'A']，则-
i：= j
返回ret
定义一个函数process()，它需要s，
对于初始化i：= 0，j：= 0，当j <s的大小时，更新（j增加1），-
i：= j
从s删除i，j-i
j：= i-1
忽略以下部分，跳至下一个迭代
如果s [i]与s [j]相同，则-
如果(j-i)> = 3，则-
除此以外
用两个字符串调用findMinStep()以获取答案
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9;
class Solution {
public:
int findMinStep(string s, string hand) {
s += "#";
vector <int> v(26);
for(int i = 0; i < hand.size(); i++){
v[hand[i] - 'A']++;
}
int ret = solve(s, v);
return ret >= INF ? -1 : ret;
}
int solve(string s, vector <int>& v){
if(s == "#") return 0;
int ret = INF;
for(int i = 0, j = 0; j < s.size(); j++){
if(s[i] == s[j]) continue;
int need = 3 - (j - i);
char x = s[i];
if(need <= v[x - 'A']){
v[x - 'A'] -= need;
ret = min( ret, need + solve(s.substr(0,i) + s.substr(j , s.size() - j), v));
v[x - 'A'] += need;
}
i = j;
}
process(s);
if(s == "#") return 0;
for(int i = 0, j = 0; j < s.size(); j++){
if(s[i] == s[j]) continue;
int need = 3 - (j - i);
char x = s[i];
if(need <= v[x - 'A']){
v[x - 'A'] -= need;
ret = min( ret, need + solve(s.substr(0,i) + s.substr(j , s.size() - j), v));
v[x - 'A'] += need;
}
i = j;
}
return ret;
}
void process(string& s){
for(int i = 0, j = 0; j < s.size(); j++){
if(s[i] == s[j]) continue;
if((j - i) >= 3){
s.erase(i, j - i);
j = i - 1;
} else i = j;
}
}
};
main(){
Solution ob;
cout << (ob.findMinStep("WRRBBW", "RBW"));
}"WRRBBW", "RBW"
输出结果
3