[LeetCode] 1003. Check If Word Is Valid After Substitutions-JZTXT

Given a string s, determine if it is valid.

A string s is valid if, starting with an empty string t = "", you can transform t into s after performing the following operation any number of times:

Insert string "abc" into any position in t. More formally, t becomes tleft + "abc" + tright, where t == tleft + tright. Note that tleft and tright may be empty.

Return true if s is a valid string, otherwise, return false.

Example 1:

Input: s = "aabcbc"
Output: true
Explanation:
"" -> "abc" -> "aabcbc"
Thus, "aabcbc" is valid.

Example 2:

Input: s = "abcabcababcc"
Output: true
Explanation:
"" -> "abc" -> "abcabc" -> "abcabcabc" -> "abcabcababcc"
Thus, "abcabcababcc" is valid.

Example 3:

Input: s = "abccba"
Output: false
Explanation: It is impossible to get "abccba" using the operation.

Constraints:

1 <= s.length <= 2 * 104
s consists of letters 'a', 'b', and 'c'

检查替换后的词是否有效。

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/check-if-word-is-valid-after-substitutions
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路是用 stack，参考20题。因为 input 字符串是由若干个 abc 进行插入操作得来的，所以如果这个 input 字符串是合法的，那么我们一定起码能找的到一个连续的子串 abc。找到这个 abc 之后，我们把它从字符串中删除，看看剩下的部分是否还能找到另一个 abc。如此循环，最终可以将整个 input 字符串删完。

xxxxxxxxxabcyyyyyyyyyy

时间O(n)

空间O(n)

Java实现

 1 class Solution {
 2     public boolean isValid(String s) {
 3         StringBuilder sb = new StringBuilder();
 4         for (char c : s.toCharArray()) {
 5             sb.append(c);
 6             int len = sb.length();
 7             if (len >= 3) {
 8                 if (sb.substring(len - 3, len).equals("abc")) {
 9                     sb.delete(len - 3, len);
10                 }
11             }
12         }
13         return sb.length() == 0;
14     }
15 }