中国建设官方网站,嘉兴品牌网站设计,网站开发如何修改字体,湘潭网站建设的公司Problem: 2696. 删除子串后的字符串最小长度 文章目录 思路解题方法复杂度Code 思路 可以知道能够消除的只有AB 和CD 的者两种排列顺序方式#xff0c;但是也许在发生一次消除后还会引发后续的消除可能性。 元素从前向后进行检测#xff0c;如果是A或者C进行标记入栈#xf… Problem: 2696. 删除子串后的字符串最小长度 文章目录 思路解题方法复杂度Code 思路 可以知道能够消除的只有AB 和CD 的者两种排列顺序方式但是也许在发生一次消除后还会引发后续的消除可能性。 元素从前向后进行检测如果是A或者C进行标记入栈然后传入的如果是与之对应的B或者D则达成消除如果不是也直接入栈每次都对栈顶元素和即将传入的元素做匹配判断匹配的消除栈顶元素下移同时继续进行匹配判断知道最后一个元素入栈最后栈内含有的元素数量就是最后得到的最小长度。 解题方法 1.建立一个栈初始化栈底0 2.将字符串的元素传入与栈顶元素做比较如果栈顶是A或者C同时即将进站的元素是B或者D那么此时对栈顶元素做弹出操作同时元素不再入栈; 3.最后返回栈的长度-1即可除去初始化的一个长度。 复杂度
时间复杂度: 时间复杂度 O ( n ) O(n) O(n) 空间复杂度: 空间复杂度 O ( n ) O(n) O(n) Code
class Solution {
public:int minLength(string s) {std::stackcharmyStack;myStack.push(0);for(int i 0 ;is.size();i){if((myStack.top()A s[i]B)||(myStack.top()C s[i]D)){myStack.pop();continue;}myStack.push(s[i]);}return myStack.size()-1;}
};
