19.10.2023
844. Backspace String Compare medium
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/375
Problem TDLR
Are typing with backspace
sequences equal
Intuition
We can use a Stack to evaluate the resulting strings. However, scanning from the end and counting backspaces would work better.
Approach
Remove all the backspaced chars before comparing
Complexity
Time complexity:
O(n)Space complexity:
O(1)
Code
fun backspaceCompare(s: String, t: String): Boolean {
var si = s.lastIndex
var ti = t.lastIndex
while (si >= 0 || ti >= 0) {
var bs = 0
while (si >= 0 && (s[si] == '#' || bs > 0))
if (s[si--] == '#') bs++ else bs--
bs = 0
while (ti >= 0 && (t[ti] == '#' || bs > 0))
if (t[ti--] == '#') bs++ else bs--
if (si < 0 != ti < 0) return false
if (si >= 0 && s[si--] != t[ti--]) return false
}
return true
}