1、題目描述
【題目鏈接】
標簽：棧 、字符串、模擬
難度：簡單
給你一個僅由 大寫 英文字符組成的字符串 s 。
你可以對此字符串執(zhí)行一些操作，在每一步操作中，你可以從 s 中刪除 任一個 “AB” 或 “CD” 子字符串。
通過執(zhí)行操作，刪除所有 “AB” 和 “CD” 子串，返回可獲得的最終字符串的 最小 可能長度。
注意，刪除子串后，重新連接出的字符串可能會產(chǎn)生新的 “AB” 或 “CD” 子串。
示例 1：
輸入：s = “ABFCACDB”
輸出：2
解釋：你可以執(zhí)行下述操作：
- 從 “ABFCACDB” 中刪除子串 “AB”，得到 s = “FCACDB” 。
- 從 “FCACDB” 中刪除子串 “CD”，得到 s = “FCAB” 。
- 從 “FCAB” 中刪除子串 “AB”，得到 s = “FC” 。
最終字符串的長度為 2 。
可以證明 2 是可獲得的最小長度。
示例 2：
輸入：s = “ACBBD”
輸出：5
解釋：無法執(zhí)行操作，字符串長度不變。
提示：
1 <= s.length <= 100
s 僅由大寫英文字母組成
2、基本思路
?這是一道簡單的字符串處理的題目，可以用棧模型上述的刪除的過程即可，值得注意的是，刪除子串后，重新連接出的字符串可能會產(chǎn)生新的 “AB” 或 “CD” 子串。文章來源：http://www.zghlxwxcb.cn/news/detail-796294.html
下面是利用棧對示例 1 模擬的過程：文章來源地址http://www.zghlxwxcb.cn/news/detail-796294.html
- 初始化棧空；
- 棧空，A入棧；
- 當前元素B，與棧頂元素A，構(gòu)成子串AB，A出棧；
- ?？眨現(xiàn)入棧；
- 當前元素C，棧頂元素F，構(gòu)不成子串，C入棧；
- 當前元素A，棧頂元素C，構(gòu)不成子串，A入棧；
- 當前元素C，棧頂元素A，構(gòu)不成子串，C入棧；
- 當前元素D，棧頂元素C，構(gòu)成子串CD，C出棧；
- 當前元素B，棧頂元素A，構(gòu)成子串AB，A出棧；
- 字符串元素遍歷完畢，棧中元素的長度即為答案；
3、代碼實現(xiàn)
int minLength(string s) {
stack<char> st;
for(int i = 0;i<s.length();++i)
{
char c = s[i];
if(st.empty())
st.push(c);
else
{
if(c=='D'&&st.top()=='C')
st.pop();
else if(c=='B'&&st.top()=='A')
st.pop();
else
st.push(c);
}
}
return st.size();
}
到了這里，關(guān)于【LeetCode2696】刪除子串后的字符串最小長度的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
