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'
Solution: Stack
If current char can be appended to the stack do so, if the top of stack is “abc” pop, otherwise push the current char to the stack. Check whether the stack is empty after all chars were processed.
Time complexity: O(n)
Space complexity: O(n)
C++
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
// Author: Huahua, running time: 28 ms, 11.9 MB class Solution { public: bool isValid(string S) { stack<string> st; for (char ch : S) { if (st.empty()) { st.push(""); } string& s = st.top(); char exp = 'a' + s.length(); if (ch == exp) { s += ch; if (s == "abc") st.pop(); } else if (ch != 'a'){ return false; } else { st.push("a"); } } return st.empty(); } }; |
请尊重作者的劳动成果,转载请注明出处!花花保留对文章/视频的所有权利。
如果您喜欢这篇文章/视频,欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
Be First to Comment