Решение задачи 844 “Backspace String Compare” с LeetCode.
Условие задачи
Даны две строки S и T, необходимо вернуть результат сравнения этих строк, если воспринимать их как последовательность напечатанных символов, где # - означает backspace.
пример 1
1
2
3
|
Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".
|
пример 2
1
2
3
|
Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".
|
пример 3
1
2
3
|
Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".
|
пример 4
1
2
3
|
Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".
|
ограничения
1 <= S.length <= 2001 <= T.length <= 200S и T содержать только буквы в нижнем регистре и #
Решение
Brute force
Идея алгоримма
Написать метод, который будет идти по заданной строке и при встрече # удалять его и предыдущий символ( если есть).
Отправить обе входных строки в этот метод и сравнить результат
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
func backspaceCompare(S string, T string) bool {
S = clear(S)
T = clear(T)
return S == T
}
func clear(S string) string {
for idx := 0; idx < len(S); idx++ {
if string(S[idx]) != "#" {
continue
}
if idx-1 >= 0 {
S = S[:idx-1] + S[idx:]
fmt.Println("->", idx, S)
idx--
}
S = S[:idx] + S[idx+1:]
idx--
}
return S
}
|
Два указателя
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
|
func backspaceCompare(S string, T string) bool {
s := len(S)-1
t := len(T)-1
sb := 0
tb := 0
for t>=0 || s>=0 {
for s >= 0 {
if string(S[s]) == "#" {
sb++
s--
} else if sb>0 {
sb--
s--
}else {
break
}
}
for t >= 0 {
if string(T[t]) == "#" {
tb++
t--
} else if tb>0 {
tb--
t--
}else {
break
}
}
if s>=0 && t>= 0&& S[s]!=T[t]{
return false
}
if (s>=0) != (t>=0) {
return false
}
s--
t--
}
return true
}
|