1003. Check If Word Is Valid After Substitutions #

Problem #

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 <= S.length <= 20000
S[i] is ‘a’, ‘b’, or ‘c’

Problem Summary #

Assume abc is a valid string. For any string V, if the string V is split into two halves, X and Y, by abc to form the string X + abc + Y, then the string X + abc + Y is still valid. X and Y can be empty strings.

For example, “abc”( "” + “abc” + “"), “aabcbc”( “a” + “abc” + “bc”), “abcabc”( "” + “abc” + “abc”), “abcabcababcc”( “abc” + “abc” + “ababcc”, where “ababcc” is also valid, “ab” + “abc” + “c”) are all valid strings.

“abccba”( "” + “abc” + “cba”, where “cba” is not a valid string), “ab”(“ab” is also not a valid string), “cababc”(“c” + “abc” + “bc”, where “c” and “bc” are both not valid strings), “bac” (“bac” is also not a valid string) are all not valid strings.

Given any string S, determine whether it is valid; if it is valid, output true.

Solution Approach #

This problem can be treated similarly to a parentheses matching problem, because a combination like “abc” represents validity, similar to matching parentheses. When encountering “a”, push it onto the stack. When encountering the character “b”, check whether the top of the stack is “a”. When encountering the character “c”, check whether the top of the stack is “a” and “b”. Finally, if the stack is empty, output true.

Code #


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
}