LeetCode_栈_中等_1003.检查替换后的词是否有效

我会带着你远行 2023-10-09 21:06 35阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个字符串 s ，请你判断它是否有效。  
字符串 s 有效需要满足：假设开始有一个空字符串 t = “” ，你可以执行 任意次 下述操作将 t 转换为 s ：

将字符串 “abc” 插入到 t 中的任意位置。形式上，t 变为 tleft + “abc” + tright，其中 t == tleft + tright 。注意，tleft 和 tright 可能为 空 。  
如果字符串 s 有效，则返回 true；否则，返回 false。

**示例 1：**  
输入：s = “aabcbc”  
输出：true  
解释：  
“” -> “abc” -> “aabcbc”  
因此，“aabcbc” 有效。

**示例 2：**  
输入：s = “abcabcababcc”  
输出：true  
解释：  
“” -> “abc” -> “abcabc” -> “abcabcabc” -> “abcabcababcc”  
因此，“abcabcababcc” 有效。

**示例 3：**  
输入：s = “abccba”  
输出：false  
解释：执行操作无法得到 “abccba” 。

**提示：**  
1 <= s.length <= 2 \* 104  
s 由字母 ‘a’、‘b’ 和 ‘c’ 组成

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/check-if-word-is-valid-after-substitutions

## 2.思路 ##

（1）删除子串 “abc”

*  首先，使用 StringBuilder 类创建一个名为 builder 的对象，该对象的值为参数 s 的值。
 *  然后，进入一个 while 循环，该循环将一直执行直到 builder 的长度为 0。在每个循环迭代中，将执行以下步骤：
    
     *  使用 indexOf 方法搜索 builder 中是否存在子字符串 “abc”。如果找到了，将返回该子字符串第一次出现的索引位置。如果未找到，将返回 -1。
     *  如果找到了子字符串 “abc”，则使用 delete 方法从 builder 中删除该子字符串。
     *  如果未找到子字符串 “abc”，则说明 builder 中不包含有效的括号匹配，因此返回 false。
 *  最终，如果 while 循环成功执行，即所有的 “abc” 子字符串都已被删除，则返回 true。

（2）栈  
遍历字符串 s，将当前访问到的字符 c 压入栈 stack 中，如果栈元素数目大于等于 3 且栈顶的 3 个元素依次等于 ‘a’、‘b’ 和 ‘c’，那么将这三个元素出栈。如果最后栈为空，则字符串 s 有效；否则字符串 s 无效。

## 3.代码实现（Java） ##

//思路1————删除子串 "abc"
    class Solution {
        
        public boolean isValid(String s) {
        
            StringBuilder builder = new StringBuilder(s);
            while (builder.length() != 0) {
        
                int index = builder.indexOf("abc");
                if (index != -1) {
        
                    builder.delete(index, index + 3);
                } else {
        
                    return false;
                }
            }
            return true;
        }
    }

//思路2————栈
    class Solution {
        
        public static boolean isValid(String s) {
        
            StringBuilder stack = new StringBuilder();
            for (int i = 0; i < s.length(); i++) {
        
                char c = s.charAt(i);
                stack.append(c);
                if (stack.length() >= 3 && stack.substring(stack.length() - 3).equals("abc")) {
        
                    stack.delete(stack.length() - 3, stack.length());
                }
            }
            return stack.isEmpty();
        }
    }