【力扣每日一题】力扣2696删除子串后的字符串最小长度
2024-01-10 10:36:27
题目来源
题目概述
给你一个仅由?大写?英文字符组成的字符串?s?。 你可以对此字符串执行一些操作,在每一步操作中,你可以从?s?中删除 任一个?"AB"?或?"CD"?子字符串。 通过执行操作,删除所有?"AB"?和?"CD"?子串,返回可获得的最终字符串的?最小?可能长度。 注意,删除子串后,重新连接出的字符串可能会产生新的?"AB"?或?"CD"?子串。
示例
示例 1:
输入:s = "ABFCACDB"
输出:2
解释:你可以执行下述操作:
- 从 "ABFCACDB" 中删除子串 "AB",得到 s = "FCACDB" 。
- 从 "FCACDB" 中删除子串 "CD",得到 s = "FCAB" 。
- 从 "FCAB" 中删除子串 "AB",得到 s = "FC" 。
最终字符串的长度为 2 。 可以证明 2 是可获得的最小长度。
示例 2:
输入:s = "ACBBD"
输出:5
解释:无法执行操作,字符串长度不变。
提示
- 1 <= s.length <= 100
- s 仅由大写英文字母组成
解题思路
- 使用栈来保存可能需要删除的前半部分子串;
- 当我们遇到A或者C时入栈,等待匹配;
- 当遇到B或D时,判断栈顶是否是对应的前一个字符,如果是则匹配成功,被删除子串长度+2,反之匹配失败,栈中的子串无法再被连续匹配,全部出栈;
- 当遇到的不是ABCD中的任何一个,栈中的子串都无法被连续匹配,全部出栈。
代码实现
java实现
public class Solution {
public int minLength(String s) {
int length = s.length();
int count = 0;
int[] arrayStack = new int[length];
int topIndex= 0;
for(int i = 0; i < length; i++) {
char current = s.charAt(i);
if (current == 'A' || current == 'C') {
// 遇到AC入栈
arrayStack[topIndex++] = current;
}else if(current == 'B' || current == 'D') {
// 栈为空,无法匹配,无视该字符
if (topIndex == 0) {
continue;
}
// 如果B前一个是A,或者D前一个是C
if (current - arrayStack[topIndex - 1] == 1) {
count += 2;
topIndex--;
}else {
topIndex = 0;
}
}else {
// 如果没有遇到ABCD出栈全部字符
topIndex = 0;
}
}
return length - count;
}
}
c++实现
class Solution {
public:
int minLength(string s) {
int length = s.length();
int count = 0;
vector<int> arrayStack = vector<int>(length);
int topIndex = 0;
for (int i = 0; i < length; i++) {
char current = s[i];
if (current == 'A' || current == 'C') {
// 遇到AC入栈
arrayStack[topIndex++] = current;
}
else if (current == 'B' || current == 'D') {
// 栈为空,无法匹配,无视该字符
if (topIndex == 0) {
continue;
}
// 如果B前一个是A,或者D前一个是C
if (current - arrayStack[topIndex - 1] == 1) {
count += 2;
topIndex--;
}
else {
topIndex = 0;
}
}
else {
// 如果没有遇到ABCD出栈全部字符
topIndex = 0;
}
}
return length - count;
}
};
运行结果
java结果
c++结果
文章来源:https://blog.csdn.net/qq_56460466/article/details/135496184
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!