LeetCode Entry

844. Backspace String Compare

19.10.2023 medium 2023 kotlin

Remove all of the backspaced chars before comparing

844. Backspace String Compare medium blog post substack image.png

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 of 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
    }