leetcode 844. 比较含退格的字符串

leetcode 844. 比较含退格的字符串

题目描述

844. 比较含退格的字符串

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例 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 = "b" 输出：false 解释：s 会变成 "c"，但 t 仍然是 "b"。

提示：

1 <= s.length, t.length <= 200 s 和 t 只含有小写字母以及字符 '#'

进阶：

你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

解题思路

法1

栈:模拟
我们使用两个栈来存储结果字符串\

当字符不为#时将字符储存进栈中,当字符为#时删除最后储存的最后

遍历数组,最后得到的结果进行比对,如果相同返回真.否则为假

• 时间复杂度(O(n))
• 空间复杂度(O(n))

执行结果

法1

使用两个栈 sStack 和 tStack 分别处理字符串 s 和 t。遍历输入的字符串，遇到字符 '#' 时，将栈顶的元素弹出，否则将字符入栈。最后，比较两个栈中剩余的元素是否相等，如果相等，则返回 true，否则返回 false。

func backspaceCompare(s string, t string) bool {
    sStack := []rune{}
    tStack := []rune{}

    for _, char := range s {
        if char == '#' {
            if len(sStack) > 0 {
                sStack = sStack[:len(sStack)-1]
            }
        } else {
            sStack = append(sStack, char)
        }
    }

    for _, char := range t {
        if char == '#' {
            if len(tStack) > 0 {
                tStack = tStack[:len(tStack)-1]
            }
        } else {
            tStack = append(tStack, char)
        }
    }

    return string(sStack) == string(tStack)
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 1.9 MB , 在所有 Go 提交中击败了 31.43% 的用户 通过测试用例： 114 / 114 炫耀一下: