Problem: 2696. 刪除子串后的字符串最小長度
思路
可以知道能夠消除的只有AB 和CD 的者兩種排列順序方式，但是也許在發(fā)生一次消除后還會引發(fā)后續(xù)的消除可能性。
- 元素從前向后進行檢測，如果是A或者C進行標記入棧，然后傳入的如果是與之對應的B或者D，則達成消除，如果不是也直接入棧；
- 每次都對棧頂元素和即將傳入的元素做匹配判斷，匹配的消除，棧頂元素下移，同時繼續(xù)進行匹配判斷；
- 知道最后一個元素入棧，最后棧內含有的元素數(shù)量就是最后得到的最小長度。
解題方法
1.建立一個棧，初始化棧底=0；
2.將字符串的元素傳入與棧頂元素做比較，如果棧頂是A或者C，同時即將進站的元素是B或者D，那么此時對棧頂元素做彈出操作，同時元素不再入棧;
3.最后返回棧的長度-1即可（除去初始化的一個長度）。
復雜度
時間復雜度:
時間復雜度 O ( n ) O(n) O(n)
空間復雜度:文章來源：http://www.zghlxwxcb.cn/news/detail-824093.html
空間復雜度 O ( n ) O(n) O(n)文章來源地址http://www.zghlxwxcb.cn/news/detail-824093.html
Code
class Solution {
public:
int minLength(string s) {
std::stack<char>myStack;
myStack.push('0');
for(int i =0 ;i<s.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;
}
};
到了這里，關于力扣2696. 刪除子串后的字符串最小長度的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網！
