class Solution {
public:
int minLength(string s) {
}
};
6439. 删除子串后的字符串最小长度
给你一个仅由 大写 英文字符组成的字符串 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 <= 100s 仅由大写英文字母组成原站题解
cpp 解法, 执行用时: 8 ms, 内存消耗: 8 MB, 提交时间: 2024-01-10 00:14:44
class Solution {
public:
int minLength(string s) {
stack<char> st;
for (char c: s) {
if (!st.empty() && (c == 'B' && st.top() == 'A' || c == 'D' && st.top() == 'C'))
st.pop();
else
st.push(c);
}
return st.size();
}
};
cpp 解法, 执行用时: 160 ms, 内存消耗: 38 MB, 提交时间: 2024-01-10 00:14:31
class Solution {
public:
int minLength(string s) {
regex ab("AB"), cd("CD");
while (s.find("AB") != string::npos || s.find("CD") != string::npos) {
s = regex_replace(s, ab, "");
s = regex_replace(s, cd, "");
}
return s.length();
}
};
rust 解法, 执行用时: 8 ms, 内存消耗: 2.1 MB, 提交时间: 2023-09-13 09:44:37
// 解法二：暴力替换
impl Solution {
pub fn min_length(s: String) -> i32 {
let mut result = s;
while result.contains("AB") || result.contains("CD") {
result = result.replace("AB", "").replace("CD", "");
}
result.len() as i32
}
}
rust 解法, 执行用时: 4 ms, 内存消耗: 2 MB, 提交时间: 2023-09-13 09:42:48
// 解法一：栈
impl Solution {
pub fn min_length(s: String) -> i32 {
let mut stack = vec![];
for c in s.chars() {
if !stack.is_empty() && ((stack[stack.len()-1] == 'A' && c == 'B') || stack[stack.len()-1] == 'C' && c == 'D') {
stack.pop();
} else {
stack.push(c);
}
}
stack.len() as i32
}
}
golang 解法, 执行用时: 4 ms, 内存消耗: 2.6 MB, 提交时间: 2023-05-22 14:34:42
func minLength(s string) int {
st := []rune{}
for _, c := range s {
if len(st) > 0 && (c == 'B' && st[len(st)-1] == 'A' || c == 'D' && st[len(st)-1] == 'C') {
st = st[:len(st)-1]
} else {
st = append(st, c)
}
}
return len(st)
}
java 解法, 执行用时: 2 ms, 内存消耗: 42.4 MB, 提交时间: 2023-05-22 14:34:28
class Solution {
public int minLength(String s) {
var st = new ArrayDeque<Character>();
for (var c : s.toCharArray()) {
if (!st.isEmpty() && (c == 'B' && st.peek() == 'A' || c == 'D' && st.peek() == 'C'))
st.pop();
else
st.push(c);
}
return st.size();
}
}
python3 解法, 执行用时: 44 ms, 内存消耗: 16 MB, 提交时间: 2023-05-22 14:34:07
class Solution:
def minLength(self, s: str) -> int:
st = []
for c in s:
if st and (c == 'B' and st[-1] == 'A' or c == 'D' and st[-1] == 'C'):
st.pop()
else:
st.append(c)
return len(st)
golang 解法, 执行用时: 8 ms, 内存消耗: 3.1 MB, 提交时间: 2023-05-22 14:33:45
func minLength(s string) int {
for strings.Contains(s, "AB") || strings.Contains(s, "CD") {
s = strings.ReplaceAll(s, "AB", "")
s = strings.ReplaceAll(s, "CD", "")
}
return len(s)
}
java 解法, 执行用时: 7 ms, 内存消耗: 42.9 MB, 提交时间: 2023-05-22 14:33:32
class Solution {
public int minLength(String s) {
while (s.contains("AB") || s.contains("CD"))
s = s.replace("AB", "").replace("CD", "");
return s.length();
}
}
python3 解法, 执行用时: 56 ms, 内存消耗: 16.1 MB, 提交时间: 2023-05-22 14:33:17
class Solution:
def minLength(self, s: str) -> int:
while "AB" in s or "CD" in s:
s = s.replace("AB", "").replace("CD", "")
return len(s)