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

概述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

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 > 011                 {12                     arrS.removeLast()13                 }14             }15             else16             {17                 arrS.append(char)18             }19         }20         21         for char in T22         {23             if char == "#"24             {25                 if arrT.count > 026                 {27                     arrT.removeLast()28                 }29             }30             else31             {32                 arrT.append(char)33             }34         }35         return arrS == arrT36     }    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 true34         } else {35             return false36         }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 += 111                 } else {12                     countS -= 113                 }14                 15                 i -= 116             }17             18             while j >= 0 && (countT > 0 || charsT[j] == "#") { 19                 if charsT[j] == "#" { 20                     countT += 121                 } else {22                     countT -= 123                 }24                 25                 j -= 126             }27             28             if i >= 0 && j >= 0 && chaRSS[i] == charsT[j] {29                 i -= 130                 j -= 1 31             } else {32                 break33             }34         }35         return i < 0 && j < 036     }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 in10             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 }

总结

以上是内存溢出为你收集整理的[Swift]LeetCode844. 比较含退格的字符串 | Backspace String Compare全部内容，希望文章能够帮你解决[Swift]LeetCode844. 比较含退格的字符串 | Backspace String Compare所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。