网站开发ui南昌百度推广公司
Java解决删除子串后的字符串最小长度
01 题目
给你一个仅由 大写 英文字符组成的字符串 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仅由大写英文字母组成
02 知识点
- 循环
- 队列
03 我的题解
public class xunhuan01 {public static void main(String[] args) {
// 测试System.out.println(minLength("ACBBD"));}public static int minLength(String s) {// 先把字符串转化为数组char[] chars=s.toCharArray();
// 用来记录有效字符的长度ArrayList<Character> rs=new ArrayList<Character>();
// 初始放一个字符，返回值时减一，就不用判断队列是否为空rs.add('c');for (int i = 0; i < chars.length; i++) {
// 记录队列最后一个的下标int num=rs.size()-1;
// 判断新入队的值和队列最后一个是否组成‘AB’或‘CD’，是则抹除队列最后一个，否则入队if (chars[i]=='B'&&rs.get(num)=='A'||chars[i]=='D'&&rs.get(num)=='C') {rs.remove(num);}else {rs.add(chars[i]);}}return rs.size()-1;}}