[Swift]LeetCode1003. 检查替换后的词是否有效 | Check If Word Is Valid After Substitutions

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

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 <= 20000S[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 <= 20000S[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 }

 

转载于:https://www.cnblogs.com/strengthen/p/10464750.html