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'

这道题说是可以给字符串的任意位置插入 “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

类似题目:

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 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation