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 int
. More formally,t
becomestleft + "abc" + tright
, wheret == tleft + tright
. Note thattleft
andtright
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'
这道题说是可以给字符串的任意位置插入 "abc" 字符串,问是否可以组成给定字符串s。其实也就等同于从给定的字符串,每次移除一个 "abc",看是否最后能变为空串。在遍历字符串的时候,当遇到字符c的时候,此时就要考虑能否移除一个 "abc",关键是要看前面两个字符是否分别为b和a,这样就必须要保存之前遍历过的字符,可以使用一个栈,利用其后进先出的特性,这里可以用一个数组来代替栈,当遇到字符c的时候,若此时数组中的元素个数小于2,或者是前面两个字符不是b和a,此时表示这个c无论如何也无法消除了,因为无法组成 "abc",直接返回 false,否则将前面两个字符移除。若遇到的不是字符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();
}
};
我们也可以不用额外的空间,直接对s进行修改,使用两个变量i和j,遍历字符串s,每次把 s[j] 赋值给 s[i],当i大于等于3,且之前的连续三个字符分别是c,b,和a的话,i自减3,这样到最后的时候若i等于0,则表示均可以移除,返回 true,参见代码如下:
解法二:
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;
}
};
这里可以写的更简洁一些,使用 STL 的 find 函数,每次查找 "abc" 子串,可以找到的话,则移除,然后再找该字串,直到无法找到位置,最后s串为空则返回 true,参见代码如下:
解法三:
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
类似题目:
参考资料:
https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/
LeetCode All in One 题目讲解汇总(持续更新中...)