题目名称

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

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

示例

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

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

题解

这道题相对来说较为简单，但是方法不对的时候容易超时，我这边的解题思路如下

  1. 已知每次插入的时候，都是插入一个字符串 abc，因此如果不包含连续的 abc 则代表该字符串无效
  2. 找到第一个 abc 字符串的序号，然后生成一个新的字符串，这个字符串是由原来的字符串去除abc 后拼接而成的
  3. 然后重复第一步和第二步操作，知道最后生成的字符串长度为0

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  if(s.length % 3 !== 0) return false
  if(s.length === 0) return true
  while(s.length) {
    let index = s.indexOf("abc")
    if(index === -1) return false
    s = s.substring(0, index) + s.substring(index + 3, s.length)
  }
  return true
};

console.log(isValid("aabcbc"), true)
console.log(isValid("abcabcababcc"), true)