返回

LeetCode 0844.比较含退格的字符串

比较含退格的字符串

LeetCode844. 比较含退格的字符串

题目描述

给定st两个字符串,当它们分别被输入到空白的文本编辑器后,如果两者相等,返回 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

退格就是移除前面的一个字符,考虑使用双指针法。当快指针发现#,慢指针退一个,否则,慢指针移动。

注意

slowIndex0时,不能回退,会索引越界产生编译错误。

代码

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
}

GitHub

Built with Hugo
Theme Stack designed by Jimmy