1003. Check if Word Is Valid After Substitutions

# 1003. Check If Word Is Valid After Substitutions#

## 题目 #

We are given that the string “abc” is valid.

From any valid string V, we may split V into two pieces X and Y such that X + Y (X concatenated with Y) is equal to V. (X or Y may be empty.) Then, X + “abc” + Y is also valid.

If for example S = “abc”, then examples of valid strings are: “abc”, “aabcbc”, “abcabc”, “abcabcababcc”. Examples of invalid strings are: “abccba”, “ab”, “cababc”, “bac”.

Return true if and only if the given string S is valid.

Example 1:

``````
Input: "aabcbc"
Output: true
Explanation:
We start with the valid string "abc".
Then we can insert another "abc" between "a" and "bc", resulting in "a" + "abc" + "bc" which is "aabcbc".

``````

Example 2:

``````
Input: "abcabcababcc"
Output: true
Explanation:
"abcabcabc" is valid after consecutive insertings of "abc".
Then we can insert "abc" before the last letter, resulting in "abcabcab" + "abc" + "c" which is "abcabcababcc".

``````

Example 3:

``````
Input: "abccba"
Output: false

``````

Example 4:

``````
Input: "cababc"
Output: false

``````

Note:

1. 1 <= S.length <= 20000
2. S[i] is ‘a’, ‘b’, or ‘c’

## 题目大意 #

“abccba”( "” + “abc” + “cba”，“cba” 不是有效的字符串), “ab”(“ab” 也不是有效字符串), “cababc”(“c” + “abc” + “bc”，“c”，“bc” 都不是有效字符串), “bac” (“bac” 也不是有效字符串)这些都不是有效的字符串。

## 代码 #

``````
package leetcode

func isValid1003(S string) bool {
if len(S) < 3 {
return false
}
stack := []byte{}
for i := 0; i < len(S); i++ {
if S[i] == 'a' {
stack = append(stack, S[i])
} else if S[i] == 'b' {
if len(stack) > 0 && stack[len(stack)-1] == 'a' {
stack = append(stack, S[i])
} else {
return false
}
} else {
if len(stack) > 1 && stack[len(stack)-1] == 'b' && stack[len(stack)-2] == 'a' {
stack = stack[:len(stack)-2]
} else {
return false
}
}
}
return len(stack) == 0
}

``````

Sep 6, 2020
Edit this page