-
Notifications
You must be signed in to change notification settings - Fork 2
/
q0844.swift
107 lines (100 loc) · 2.56 KB
/
q0844.swift
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
//
// q0844.swift
// LeetcodeSwift
//
// Created by NowOrNever on 09/04/2020.
// Copyright © 2020 DL. All rights reserved.
//
import Foundation
//844. Backspace String Compare
//Easy
//
//1129
//
//63
//
//Add to List
//
//Share
//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?
//Accepted
//113,364
//Submissions
//239,093
class q0844Solution {
var sCharacters = [Character]()
var tCharacters = [Character]()
func nextC(characters:[Character], index: Int) -> Int {
var countHash = 0
var _index = index
while _index >= 0 {
if characters[_index] == "#" {
countHash += 1
}else if(countHash > 0){
countHash -= 1
}else{
return _index
}
_index -= 1
}
return -1
}
func backspaceCompare(_ S: String, _ T: String) -> Bool {
sCharacters = [Character].init(S)
tCharacters = [Character].init(T)
var sIndex = sCharacters.count - 1
var tIndex = tCharacters.count - 1
while sIndex >= 0 && tIndex >= 0 {
sIndex = nextC(characters: sCharacters, index: sIndex)
tIndex = nextC(characters: tCharacters, index: tIndex)
if sIndex >= 0 && tIndex >= 0 && sCharacters[sIndex] != tCharacters[tIndex] {
return false
}
sIndex -= 1
tIndex -= 1
}
if sIndex >= 0 && sCharacters[sIndex] == "#"{
sIndex = nextC(characters: sCharacters, index: sIndex)
}
if tIndex >= 0 && tCharacters[tIndex] == "#" {
tIndex = nextC(characters: tCharacters, index: tIndex)
}
return sIndex == tIndex
}
}
func q0844() -> () {
let solution = q0844Solution()
let S = "rheyggodcclgstf"
let T = "#rheyggodcclgstf"
let result = solution.backspaceCompare(S, T)
print(result)
}