比较含退格的字符串
LeetCode844. 比较含退格的字符串
题目描述
给定s
和t
两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回 true
。#
代表退格字符。
注意:如果对空文本输入退格字符,文本继续为空。
示例 1:
1
2
3
|
输入:s = "ab#c", t = "ad#c"
输出:true
解释:s 和 t 都会变成 "ac"。
|
示例 2:
1
2
3
|
输入:s = "ab##", t = "c#d#"
输出:true
解释:s 和 t 都会变成 ""。
|
示例 3:
1
2
3
|
输入:s = "a#c", t = "b"
输出:false
解释:s 会变成 "c",但 t 仍然是 "b"。
|
思路
题目要求:
- 输入两个含退格的字符串,比较是否相等
- 相等输出
true
,反之输出false
退格就是移除前面的一个字符,考虑使用双指针法。当快指针发现#
,慢指针退一个,否则,慢指针移动。
注意
当slowIndex
为0
时,不能回退,会索引越界产生编译错误。
代码
Go
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
|
func backspaceCompare(s string, t string) bool {
sNew := getString(s)
tNew := getString(t)
if sNew == tNew {
return true
} else {
return false
}
}
func getString(s string) string {
tempArray := []string{}
for _, item := range s {
tempArray = append(tempArray, string(item))
}
slowIndex := 0
for fastIndex := 0; fastIndex < len(tempArray); fastIndex++ {
if s[fastIndex] != '#' {
tempArray[slowIndex] = tempArray[fastIndex]
slowIndex += 1
} else if slowIndex != 0 {
slowIndex -= 1
}
}
if slowIndex == 0 {
return ""
}
var result string
for i := 0; i < slowIndex; i++ {
result += tempArray[i]
}
return result
}
|
Link
GitHub