Java解决删除子串后的字符串最小长度

小鱼儿 2024-02-05 23:23 32阅读 0赞

## 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 <= 100`
 *  `s` 仅由大写英文字母组成

### 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;
    	 }
    
    }