检查替换后的词是否有效

难度: Medium

给你一个字符串 s ，请你判断它是否有效。

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

将字符串 "abc" 插入到 t 中的任意位置。形式上，t 变为 t_left + "abc" + t_right，其中 t == t_left + t_right 。注意，t_left 和 t_right 可能为空。

如果字符串 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 * 10⁴
s 由字母 'a'、'b' 和 'c' 组成

Submission

运行时间: 28 ms

内存: 16.1 MB

class Solution:
    def isValid(self, s: str) -> bool:
        while ('abc' in s):
            s = s.replace('abc','')
        return True if len(s) == 0 else False

Explain

题解的核心思路是通过一个循环逐渐移除字符串 's' 中所有连续的 'abc' 子串。这个过程使用 Python 字符串的 'replace' 方法，每次发现子串 'abc' 就将其替换为空字符串，即删除。循环继续进行，直到字符串中不再包含 'abc'。最后，如果字符串为空，说明原字符串可以完全由 'abc' 通过指定操作构成，因此返回 True；否则返回 False。

时间复杂度: O(n^2)

空间复杂度: O(n)

class Solution:
    def isValid(self, s: str) -> bool:
        # 循环检查字符串s中是否含有子串'abc'
        while ('abc' in s):
            # 将所有的'abc'替换为空字符串，即删除这些子串
            s = s.replace('abc', '')
        # 如果最终字符串s为空，则说明s可以由'abc'完全构成，返回True；否则返回False
        return True if len(s) == 0 else False

Explore

在这个特定的问题中，使用循环加字符串替换的方式是一个直观的解决方案，因为它允许直接地移除目标模式（'abc'），并且这种方法在代码实现上简洁明了。使用栈虽然同样可以解决问题，但在某些情况下可能需要更多的操作来处理栈的入栈和出栈，尤其是在处理连续模式匹配时。然而，从性能角度考虑，使用栈可能在处理大规模数据时表现更好，因为字符串替换需要频繁的内存操作和可能的字符串重新构建。

使用`'abc' in s`进行子串检查本身是一个线性时间操作，即O(n)，其中n是字符串s的长度。在每次替换操作后，字符串长度可能会减少，但是在最坏情况下（例如字符串为'aaa...aabbb...bcc...'），每次替换只删除很少的字符，这将导致多次全字符串扫描，使得总体时间复杂度接近O(n^2)。因此，这种方法在处理非常长的字符串时可能效率低下。

是的，这种解法仍然有效。解法的核心是移除所有的'abc'子串，不管它们出现的位置或次数。例如对于字符串'ababc'，在第一轮循环中'abc'被移除，留下'ab'，由于不再包含'abc'，循环停止，最终返回False，正确地表明原字符串不能完全由'abc'构成。

在实际应用中，使用栈处理字符串的方法通常更优，特别是当需要处理大规模或复杂的字符串数据时。使用栈可以在遍历字符串的同时进行模式匹配和数据处理，通常只需要一次扫描即可完成，因此时间复杂度为O(n)。而循环加字符串替换的方法虽然代码简单，却可能涉及多次扫描和高开销的字符串操作，特别是在字符串长度很长或模式较难匹配的情况下。因此，从性能和效率角度看，使用栈的方法更具优势。