[Swift]LeetCode1003.检查替换后的词是否有效|CheckIfWordIsValidAfterSubstitutions ...

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10464750.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

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: 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: 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: false

Example 4:

Input: false

Note:

1 <= S.length <= 20000
S[i] is 'a', 'b', or 'c'

给定有效字符串 "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。

示例 1：

输入："aabcbc"
输出：true
解释：
从有效字符串 "abc" 开始。
然后我们可以在 "a" 和 "bc" 之间插入另一个 "abc"，产生 "a" + "abc" + "bc"，即 "aabcbc"。

示例 2：

输入："abcabcababcc"
输出：true
解释：
"abcabcabc" 是有效的，它可以视作在原串后连续插入 "abc"。
然后我们可以在最后一个字母之前插入 "abc"，产生 "abcabcab" + "abc" + "c"，即 "abcabcababcc"。

示例 3：

输入："abccba"
输出：false

示例 4：

输入："cababc"
输出：false

提示：

1 <= S.length <= 20000
S[i] 为 'a'、'b'、或 'c'

44ms

 1 class Solution 
 2 {    
 3     func isValid( _ string: String ) -> Bool 
 4     {        
 5         var aStack: Int = 0
 6         var bStack: Int = 0      
 7         for char in string.characters
 8         {            
 9             if char == "a"
10             {
11                 aStack += 1
12             }
13             else if char == "b"
14             {                
15                 bStack += 1                
16                 if bStack > aStack
17                 {
18                     return false
19                 }                
20             }
21             else if char == "c"
22             {                
23                 aStack -= 1
24                 bStack -= 1                
25                 if aStack < 0 || bStack < 0
26                 {
27                     return false
28                 }                
29             }            
30         }        
31         return aStack == 0 && bStack == 0        
32     }    
33 }

52ms

 1 class Solution {
 2     func isValid(_ S: String) -> Bool {
 3         var stack = [Character]()
 4         for char in S {
 5             if char == "c" {
 6                 guard stack.count >= 2 else { return false }
 7                 guard stack.removeLast() == "b" else { return false }
 8                 guard stack.removeLast() == "a" else { return false }
 9             } else {
10                 stack.append(char)
11             }
12         }
13         return stack.count == 0
14     }
15 }

56ms

 1 class Solution {
 2     func isValid(_ S: String) -> Bool {
 3         var stack: [Character] = []
 4         for s in S {
 5             switch s {
 6             case "a", "b": stack.append(s)
 7             case "c":
 8                 guard stack.count >= 2,
 9                     stack.removeLast() == "b",
10                     stack.removeLast() == "a" else {
11                     return false
12                 }
13             default: fatalError()
14             }
15         }
16         
17         return stack.isEmpty
18     }
19 }

80ms

 1 class Solution {
 2     func isValid(_ S: String) -> Bool {
 3         let s = Array(S)
 4         var v = [Character]()
 5         var j = 0
 6         while j < s.count {
 7             v.append(s[j])
 8             if v.count >= 3 && 
 9                 v[v.count - 3] == "a" &&
10                 v[v.count - 2] == "b" &&
11                 v[v.count - 1] == "c" {
12                 v.removeLast(3)
13             }
14             j += 1
15         }
16         return v.count == 0
17     }
18 }

288ms

1 class Solution {
2     func isValid(_ S: String) -> Bool {
3         var S = S
4         while S.contains("abc") {
5             S = S.replacingOccurrences(of: "abc", with: "", options: .literal, range: nil)
6         }
7         return S.isEmpty
8     }
9 }

292ms

 1 class Solution {
 2     func isValid(_ S: String) -> Bool {
 3         var curS = S
 4         while curS.count >= 3 {
 5             let str = (curS as NSString).replacingOccurrences(of: "abc", with: "") 
 6                                                               
 7             curS = str       
 8             if !(str as NSString).contains("abc") { break}
 9         }
10         return curS.count == 0
11     }
12 }