1003-检查替换后的词是否有效

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:25 2023-09-13 16:06:25 Updated    

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

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

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

如果字符串 s 有效，则返回 true；否则，返回 false。

示例 1：

**输入：** s = "aabcbc"
**输出：** true
**解释：**
"" -> " **abc** " -> "a **abc** bc"
因此，"aabcbc" 有效。

示例 2：

**输入：** s = "abcabcababcc"
**输出：** true
**解释：**
"" -> " **abc** " -> "abc **abc** " -> "abcabc **abc** " -> "abcabcab **abc** c"
因此，"abcabcababcc" 有效。

示例 3：

**输入：** s = "abccba"
**输出：** false
**解释：** 执行操作无法得到 "abccba" 。

提示：

  • 1 <= s.length <= 2 * 104
  • s 由字母 'a'、'b' 和 'c' 组成

方法一：栈

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

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    bool isValid(string s) {
        string stk;
        for (auto c : s) {
            stk.push_back(c);
            if (stk.size() >= 3 && stk.substr(stk.size() - 3, 3) == "abc") {
                stk.erase(stk.end() - 3, stk.end());
            }
        }
        return stk.empty();
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isValid(String s) {
        StringBuilder stk = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            stk.append(c);
            if (stk.length() >= 3 && stk.substring(stk.length() - 3).equals("abc")) {
                stk.delete(stk.length() - 3, stk.length());
            }
        }
        return stk.isEmpty();
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
class Solution:
    def isValid(self, s: str) -> bool:
        stk = []
        for c in s:
            stk.append(c)
            if ''.join(stk[-3:]) == "abc":
                stk[-3:] = []
        return len(stk) == 0
[sol1-C#]
1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public bool IsValid(string s) {
        StringBuilder stk = new StringBuilder();
        foreach (char c in s) {
            stk.Append(c);
            if (stk.Length >= 3 && stk.ToString().Substring(stk.Length - 3).Equals("abc")) {
                stk.Remove(stk.Length - 3, 3);
            }
        }
        return stk.Length == 0;
    }
}
[sol1-Golang]
1
2
3
4
5
6
7
8
9
10
func isValid(s string) bool {
    stk := []byte{}
    for i, _ := range s {
        stk = append(stk, s[i])
        if len(stk) >= 3 && string(stk[len(stk) - 3:]) == "abc" {
            stk = stk[:len(stk) - 3]
        }
    }
    return len(stk) == 0
}
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
bool isValid(char * s) {
    int len = strlen(s);
    int top = 0;
    char stack[len];
    for (int i = 0; i < len; i++) {
        char c = s[i];
        stack[top++] = c;
        if (top >= 3 && strncmp(stack + top - 3, "abc", 3) == 0) {
            top -= 3;
        }
    }
    return top == 0;
}
[sol1-JavaScript]
1
2
3
4
5
6
7
8
9
10
11
var isValid = function(s) {
    const stk = [];
    for (let i = 0; i < s.length; i++) {
        const c = s[i];
        stk.push(c);
        if (stk.length >= 3 && stk.slice(stk.length - 3).join("") === "abc") {
            stk.splice(stk.length - 3, 3);
        }
    }
    return stk.length === 0;
};

复杂度分析

  • 时间复杂度：O(n)，其中 n 是字符串 s 的长度。

  • 空间复杂度：O(n)。栈需要占用 O(n) 的空间。

 Comments
On this page
1003-检查替换后的词是否有效