在C ++中删除字符串II中的所有相邻重复项
假设给出了字符串s,则ak重复删除包括从字符串s中选择k个相邻且相等的字母,然后删除它们,使删除的子字符串的左侧和右侧连接在一起。我们将在给定的字符串s上重复进行k次重复删除,直到无法更改任何剩余项为止。完成所有此类重复删除后,我们必须找到最终字符串。因此,如果输入类似于s=“deeedbbcccbdaa”,且k=3,则输出将为“aa”,首先删除“eee”和“ccc”,我们将得到“ddbbbaa”,然后删除“bbb”,字符串将是“dddaa”,然后删除“ddd”,输出将是“aa”
为了解决这个问题,我们将遵循以下步骤-
ans:=空字符串
为char-int对创建一个堆栈,n:=字符串的大小
当我的范围是0到n
x:=s[i]
如果堆栈不为空并且堆栈顶部元素的整数=k,则从堆栈中删除顶部元素
如果i=n,则破坏
如果堆栈为空或堆栈顶部的字符不是x,则将对(x,1)插入堆栈,并将i加1
否则增加栈顶元素的整数部分,并将i增加1
当堆栈不为空时
ans:=ans+temp的字符部分
将温度的整数部分减少1
temp:=堆栈顶部元素
虽然temp的整数部分不为0,
从堆栈中删除顶部元素
反转ans字符串并返回。
让我们看下面的实现以更好地理解-
示例
#include <bits/stdc++.h> using namespace std; class Solution { public: string removeDuplicates(string s, int k) { string ans = ""; stack < pair<char, int> > st; int n = s.size(); for(int i = 0; i <= n;){ char x = s[i]; if(!st.empty() && st.top().second == k)st.pop(); if(i == n)break; if(st.empty() || st.top().first != x){ st.push({x, 1}); i++; } else { st.top().second++; i++; } } while(!st.empty()){ pair <char, int> temp = st.top(); while(temp.second--) ans += temp.first; st.pop(); } reverse(ans.begin(), ans.end()); return ans; } }; main(){ Solution ob; cout <<(ob.removeDuplicates("deeedbbcccbdaa", 3)); }
输入项
"deeedbbcccbdaa" 3
输出结果
aa