[Swift]LeetCode844. 比较含退格的字符串 | Backspace String Co

发布时间：2020-12-14 04:58:52 所属栏目：百科来源：网络整理

导读：Given two?strings? S ?and? T ,?return if they are equal when both are typed into empty text editors.? # ?means a backspace character. Example 1: Input: S = "ab#c",T = "ad#c" Output: true Explanation: Both S and T become "ac". Example 2: In

Given two?strings?S?and?T,?return if they are equal when both are typed into empty text editors.?#?means a backspace character.

Example 1:

Input: S = "ab#c",T = "ad#c" Output: true Explanation: Both S and T become "ac".

Example 2:

Input: S = "ab##",T = "c#d#" Output: true Explanation: Both S and T become "".

Example 3:

Input: S = "a##c",T = "#a#c" Output: true Explanation: Both S and T become "c".

Example 4:

Input: S = "a#c",T = "b" Output: false Explanation: S becomes "c" while T becomes "b".

Note:

1 <= S.length <= 200
1 <= T.length <= 200
S?and?T?only contain?lowercase letters and?‘#‘?characters.

Follow up:

Can you solve it in?O(N)?time and?O(1)?space?

给定?S?和?T?两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。?#?代表退格字符。

示例 1：

输入：S = "ab#c",T = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。

示例 2：

输入：S = "ab##",T = "c#d#"
输出：true
解释：S 和 T 都会变成 “”。

示例 3：

输入：S = "a##c",T = "#a#c"
输出：true
解释：S 和 T 都会变成 “c”。

示例 4：

输入：S = "a#c",T = "b"
输出：false
解释：S 会变成 “c”，但 T 仍然是 “b”。

提示：

1 <= S.length <= 200
1 <= T.length <= 200
S?和?T?只含有小写字母以及字符?‘#‘。

Runtime:?8 ms

Memory Usage:?19.5 MB

 1 class Solution {
 2     func backspaceCompare(_ S: String,_ T: String) -> Bool 
 3     {
 4         var arrS = [Character]()
 5         var arrT = [Character]()
 6         for char in S
 7         {
 8             if char == "#"
 9             {
10                 if arrS.count > 0
11                 {
12                     arrS.removeLast()
13                 }
14             }
15             else
16             {
17                 arrS.append(char)
18             }
19         }
20         
21         for char in T
22         {
23             if char == "#"
24             {
25                 if arrT.count > 0
26                 {
27                     arrT.removeLast()
28                 }
29             }
30             else
31             {
32                 arrT.append(char)
33             }
34         }
35         return arrS == arrT
36     }    
37 }

8ms

 1 class Solution {
 2     // S2: two pointers space could be 1
 3     // S1: M+N
 4     func backspaceCompare(_ S: String,_ T: String) -> Bool {
 5         return process(S) == process(T)    
 6     }
 7     
 8     private func process(_ S: String) -> String {
 9         var stack = [Character]()
10         for c in Array(S) {
11             if c == "#" {
12                 if stack.count > 0 {
13                     stack.removeLast()
14                 }
15             } else {
16                 stack.append(c)
17             }
18         }
19         return String(stack)
20     }
21 }

12ms

 1 class Solution {
 2     func backspaceCompare(_ S: String,_ T: String) -> Bool {
 3         var sStack: [Character] = []
 4         var tStack: [Character] = []
 5 
 6         var sArray = Array(S)
 7         var tArray = Array(T)
 8         
 9         for char in sArray {
10             if(char != "#") {
11                 sStack.append(char)
12             } else {
13                 if(!sStack.isEmpty) {
14                     sStack.removeLast()   
15                 }
16             }
17         }
18         
19         for char in tArray {
20             if(char != "#") {
21                 tStack.append(char)
22             } else {
23                 if(!tStack.isEmpty) {
24                     tStack.removeLast()   
25                 }
26             }
27         }
28         
29         print(String(sStack))
30         print(String(tStack))
31         
32         if(String(sStack) == String(tStack)) {
33             return true
34         } else {
35             return false
36         }
37     }
38 }

16ms

 1 class Solution {
 2     func backspaceCompare(_ S: String,_ T: String) -> Bool {
 3         var charsS = Array(S),charsT = Array(T)
 4         
 5         var i = charsS.count - 1,j = charsT.count - 1
 6         var countS = 0,countT = 0
 7         while i >= 0 || j >= 0 {
 8             while i >= 0 && (countS > 0 || charsS[i] == "#") { 
 9                 if charsS[i] == "#" { 
10                     countS += 1
11                 } else {
12                     countS -= 1
13                 }
14                 
15                 i -= 1
16             }
17             
18             while j >= 0 && (countT > 0 || charsT[j] == "#") { 
19                 if charsT[j] == "#" { 
20                     countT += 1
21                 } else {
22                     countT -= 1
23                 }
24                 
25                 j -= 1
26             }
27             
28             if i >= 0 && j >= 0 && charsS[i] == charsT[j] {
29                 i -= 1
30                 j -= 1 
31             } else {
32                 break
33             }
34         }
35         return i < 0 && j < 0
36     }
37 }

24ms

 1 class Solution {
 2     func backspaceCompare(_ S: String,_ T: String) -> Bool {
 3         return backspace(S) == backspace(T)
 4     }
 5     
 6     func backspace(_ string: String) -> String {
 7         var s = [Character]()
 8 
 9         string.forEach { c in
10             if c == "#" {
11                 if !s.isEmpty {
12                     s.removeLast()
13                 }
14             } else {
15                 s.append(c)
16             }
17         }
18         return String(s)
19     }
20 }

24ms

 1 class Solution {
 2     func backspaceCompare(_ S: String,_ T: String) -> Bool {
 3         let sRe = reStack(str: S)
 4         let tRe = reStack(str: T)
 5         return sRe == tRe;
 6     }
 7     
 8     public func reStack(str: String) -> String {
 9         var result = [Character]()
10         for i in str {
11             if (!result.isEmpty) {
12                 if i != "#" {
13                     result.append(i)
14                 } else {
15                     result.removeLast()
16                 }
17             } else {
18                 if i != "#" {
19                     result.append(i)
20                 }
21             }
22         }
23         return String.init(result);
24     }
25 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!