題目

給定有效字串 "abc"。

對於任何有效的字串 V，我們可以將 V 分成兩個部分 X 和 Y，使得 X + Y（X 與 Y 連線）等於 V。

（X 或 Y 可以為空。）那麼，X + "abc" + Y 也同樣是有效的。

例如，如果 S = "abc"，則有效字串的示例是："abc"，"aabcbc"，"abcabc"，"abcabcababcc"。

無效字串的示例是："abccba"，"ab"，"cababc"，"bac"。

如果給定字串 S 有效，則返回 true；否則，返回 false。

示例 1：輸入："aabcbc" 輸出：true

解釋：從有效字串 "abc" 開始。

然後我們可以在 "a" 和 "bc" 之間插入另一個 "abc"，產生 "a" + "abc" + "bc"，即 "aabcbc"。

示例 2：輸入："abcabcababcc" 輸出：true

解釋："abcabcabc" 是有效的，它可以視作在原串後連續插入 "abc"。

然後我們可以在最後一個字母之前插入 "abc"，產生 "abcabcab" + "abc" + "c"，即 "abcabcababcc"。

示例 3：輸入："abccba" 輸出：false

示例 4：輸入："cababc" 輸出：false

提示：1 <= S.length <= 20000

S[i] 為 'a'、'b'、或 'c'

解題思路分析

1、棧輔助；時間複雜度O(n)，空間複雜度O(n)

func isValid(s string) bool {	stack := make([]byte, 0)	for i := 0; i < len(s); i++ {		stack = append(stack, s[i])		if len(stack) >= 3 && string(stack[len(stack)-3:]) == "abc" {			stack = stack[:len(stack)-3]		}	}	return len(stack) == 0}

2、內建函式；時間複雜度O(n)，空間複雜度O(n)

func isValid(s string) bool {	for strings.Contains(s, "abc") {		s = strings.ReplaceAll(s, "abc", "")	}	return s == ""}

總結

Medium題目，題目比較簡單