Description
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.
给定有效字符串 "abc"。
对于任何有效的字符串 V，我们可以将 V 分成两个部分 X 和 Y，使得 X + Y（X 与 Y 连接）等于 V。（X 或 Y 可以为空。）那么，X + "abc" + Y 也同样是有效的。
例如，如果 S = "abc"，则有效字符串的示例是："abc"，"aabcbc"，"abcabc"，"abcabcababcc"。无效字符串的示例是："abccba"，"ab"，"cababc"，"bac"。
如果给定字符串 S 有效，则返回 true；否则，返回 false。
题目链接：https://leetcode.com/problems/check-if-word-is-valid-after-substitutions/
Difficulty: medium
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’
分析
- 每次遍历S，judge为True表示上一次遍历中包含“abc”；
- 若当前位置加上后两位为“abc”，则指针往后移动三位，judge置为True；
- 反之加入到s中；
- 遍历完成，s赋值S；
- 直至S为“”（返回True），或者某一个遍历没有得到“abc”字串（返回False）。
参考代码
class Solution(object):
def isValid(self, S):
judge=True
while(len(S) > 0 and judge):
i=0
s=''
judge=False
while(i<len(S)):
if(i<len(S)-2 and S[i:i+3]=='abc'):
i+=3
judge=True
else:
s+=S[i]
i+=1
S=s
if(len(S)==0):
return True
return False