[Swift]LeetCode1209.删除字符串中的所有相邻重复项II|RemoveAllAdjacentDuplicatesin ...

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

[Swift]LeetCode1209.删除字符串中的所有相邻重复项II|RemoveAllAdjacentDuplicatesin ...

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

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

Given a string s, a k duplicate removal consists of choosing k adjacent and equal letters from s and removing them causing the left and the right side of the deleted substring to concatenate together.

We repeatedly make k duplicate removals on s until we no longer can.

Return the final string after all such duplicate removals have been made.

It is guaranteed that the answer is unique.

Example 1:

Input: s = "abcd", k = 2
Output: "abcd"
Explanation: There's nothing to delete.

Example 2:

Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation: 
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"

Example 3:

Input: s = "pbbcggttciiippooaais", k = 2
Output: "ps"

Constraints:

1 <= s.length <= 10^5
2 <= k <= 10^4
s only contains lower case English letters.

给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。

在执行完所有删除操作后，返回最终得到的字符串。

本题答案保证唯一。

示例 1：

输入：s = "abcd", k = 2
输出："abcd"
解释：没有要删除的内容。

示例 2：

输入：s = "deeedbbcccbdaa", k = 3
输出："aa"
解释： 
先删除 "eee" 和 "ccc"，得到 "ddbbbdaa"
再删除 "bbb"，得到 "dddaa"
最后删除 "ddd"，得到 "aa"

示例 3：

输入：s = "pbbcggttciiippooaais", k = 2
输出："ps"

提示：

1 <= s.length <= 10^5
2 <= k <= 10^4
s 中只含有小写英文字母。

Runtime: 84 ms

Memory Usage: 21.5 MB

 1 class Solution {
 2     func removeDuplicates(_ s: String, _ k: Int) -> String {
 3         var st:[Character] = [Character]()
 4         var cnt:[Int] = [Int]()
 5         for c in s
 6         {
 7             if st.count > 0 && st.last! == c
 8             {
 9                 cnt[cnt.count - 1] += 1
10             }
11             else
12             {
13                 st.append(c)
14                 cnt.append(1)
15             }
16             while(st.count > 0 && cnt.last! == k)
17             {
18                 st.removeLast()
19                 cnt.removeLast()
20             }
21         }
22         var ret:String = String()
23         for i in 0..<st.count
24         {
25             ret += String(repeating:st[i],count:cnt[i])
26         }
27         return ret
28     }
29 }

32ms

 1 class Solution {
 2     func removeDuplicates(_ s: String, _ k: Int) -> String {
 3                
 4         if k <= 1 {
 5             return ""
 6         }
 7         if s.count < 1 {
 8             return s
 9         }
10         var chars = Array(s)
11 
12         func remove(_ chars: inout [Character]) {
13             if chars.count < k {
14                 return
15             }
16 
17             var ct = 1
18             var idx = -1
19             for i in 1..<chars.count {
20                 if chars[i] == chars[i-1] {
21                     ct += 1
22                 } else {
23                     ct = 1
24                 }
25 
26                 if ct >= k {
27                     idx = i
28                     break
29                 }
30             }
31 
32             if idx != -1 {
33                 chars.removeSubrange(idx-k+1...idx)
34                 // print(chars)
35                 remove(&chars)
36             }
37         }
38         remove(&chars)
39         return String(chars)
40     }
41 }

36ms

 1 class Solution {
 2     func removeDuplicates(_ s: String, _ k: Int) -> String {
 3         var stack = [Character]()
 4         var count = 1
 5         for c in s {
 6             stack.append(c)
 7             
 8             if stack.count > 1 {
 9                 if stack[stack.count - 1] == stack[stack.count - 2] {
10                     count += 1
11                     if count == k {
12                         stack.removeLast(k)
13                         if !stack.isEmpty {
14                             count = 0
15                             var i = stack.count - 1
16                             let last = stack[i]
17                             while i >= 0, stack[i] == last {
18                                 count += 1
19                                 i -= 1
20                             }
21                         } else {
22                             count = 1
23                         }
24                     }
25                 } else {
26                     count = 1
27                 }
28             }
29         }
30         
31         return String(stack)
32     }
33 }

40ms

 1 class Solution {
 2     func removeDuplicates(_ s: String, _ k: Int) -> String {
 3         
 4         guard k > 1 else { return "" }
 5         var stack = Array(s)
 6         
 7         var arr = [Int](repeating: 0, count: s.count)
 8         
 9         var end = 0
10         for c in s {
11             stack[end] = c
12             if end == 0 {
13                 arr[end] = 1
14             } else if stack[end] == stack[end-1] {
15                 arr[end] = arr[end-1] + 1
16             } else {
17                 arr[end] = 1
18             }
19             
20             while end + 1 >= k && arr[end] == k {
21                 end = end + 1 - k - 1
22             }
23             end += 1
24         }
25         return String(stack[0..<end])
26     }
27 }

56ms

 1 class Solution {
 2     func removeDuplicates(_ s: String, _ k: Int) -> String {
 3         var stack: [(character: Character, count: Int)] = []
 4         
 5         for c in s {
 6             guard let last = stack.last, last.character == c else {
 7                 stack.append((c, 1))
 8                 continue
 9             }
10             
11             if last.count == k - 1 {
12                 _ = stack.removeLast()
13             } else {
14                 stack[stack.count - 1] = (c, last.count + 1)
15             }
16         }
17         
18         var ans: String = ""
19         for value in stack {
20             ans.append(contentsOf: String(repeating: value.character, count: value.count))
21         }
22         
23         return ans
24     }
25 }