# 1003. Check If Word Is Valid After Substitutions

Given a string `s`, determine if it is valid.

A string `s` is valid if, starting with an empty string `t = ""`, you can transform `t` into `s` after performing the following operation any number of times:

• Insert string `"abc"` into any position in `t`. More formally, `t` becomes `tleft + "abc" + tright`, where `t == tleft + tright`. Note that `tleft` and `tright` may be empty.

Return `true`  if `s`  is a valid string, otherwise, return `false`.

Example 1:

``````Input: s = "aabcbc"
Output: true
Explanation:
"" -> "abc" -> "aabcbc"
Thus, "aabcbc" is valid.
``````

Example 2:

``````Input: s = "abcabcababcc"
Output: true
Explanation:
"" -> "abc" -> "abcabc" -> "abcabcabc" -> "abcabcababcc"
Thus, "abcabcababcc" is valid.
``````

Example 3:

``````Input: s = "abccba"
Output: false
Explanation: It is impossible to get "abccba" using the operation.
``````

Example 4:

``````Input: s = "cababc"
Output: false
Explanation: It is impossible to get "cababc" using the operation.
``````

Constraints:

• `1 <= s.length <= 2 * 104`
• `s` consists of letters `'a'``'b'`, and `'c'`

``````class Solution {
public:
bool isValid(string s) {
vector<char> st;
for (char c : s) {
if (c == 'c') {
int n = st.size();
if (n < 2 || st[n - 1] != 'b' || st[n - 2] != 'a') return false;
st.pop_back(); st.pop_back();
} else {
st.push_back(c);
}
}
return st.empty();
}
};
``````

``````class Solution {
public:
bool isValid(string s) {
int i = 0, n = s.size();
for (int j = 0; j < n; ++j) {
s[i++] = s[j];
if (i >= 3 && s[i - 3] == 'a' && s[i - 2] == 'b' && s[i - 1] == 'c') i -= 3;
}
return i == 0;
}
};
``````

``````class Solution {
public:
bool isValid(string s) {
for (auto pos = s.find("abc"); pos != string::npos; pos = s.find("abc")) {
s.erase(pos, 3);
}
return s.empty();
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1003

Valid Parentheses

https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/

https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/discuss/247548/C%2B%2B-3-lines-search-and-remove

https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/discuss/1002730/C%2B%2B-Short-O(N)-Time-O(1)-Space

https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/discuss/247626/JavaPythonC%2B%2B-Stack-Solution-O(N)

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation