Skip to content

844.backspace-string-compare.md

Latest commit

 

History

History
172 lines (137 loc) · 6.22 KB

844.backspace-string-compare.md

File metadata and controls

172 lines (137 loc) · 6.22 KB

844. Backspace String Compare

Hints

  • Think about how to process the backspace characters (#) to get the final string.
  • Can you process the strings from the end to avoid the complexity of forward processing?
  • What happens when you have multiple consecutive backspace characters?

Breakdowns

  1. How do you handle the backspace character (#) when processing from left to right?
  • Use a stack: push characters, pop when encountering #. This simulates the actual backspace behavior.
  1. How do you process the strings efficiently without building the entire final strings?
  • Process from the end using two pointers, simulating backspace operations in reverse order.
  1. How do you handle multiple consecutive backspace characters?
  • Keep a counter for backspace characters and skip the appropriate number of characters.

Stack

Build the final strings by simulating backspace operations using a stack, then compare the results.

fun backspaceCompare(s: String, t: String): Boolean {
    val sStr = buildString(s)
    val tStr = buildString(t)
    return sStr == tStr
}

private fun buildString(s: String): String {
    val str = ArrayDeque<String>()
    for (c in s) {
        if (c == '#') {
            if (str.isNotEmpty())
                str.removeLast()
        } else {
            str.addLast(c.toString())
        }
    }
    return str.joinToString("")
}
  • Time Complexity: O(s + t).
  • Space Complexity: O(s + t).

Two Pointers

We can use two pointers approach to compare two strings after applying backspace operations.

When processing from the end:

  • Each # character tells us to skip the next non-# character
  • We can use a counter to track how many characters to skip
  • This allows us to find the "effective" character at each position without storing the entire processed string
// Process `s`
s = "...ab#"
          <---
// After backspace,
s = "...a"

// Process `t`
t = "...aj#jjj###"
             <---
// After backspace,
t = "...a"

// Then compare two strings after backspacing
if (s[i] != t[j]) return false

There are three cases when we encounter a character:

  • When we encounter #, then we have to skip the next non-# character. We use skipS and skipT to track the number of backspace.
  • When we encounter non-# character, then we have to check if we have to backspace it. If yes, we backspace, otherwise we compare two characters.

After backspacing, we compare two characters: If two characters are not equal or one of the string is empty, then we return false.

fun backspaceCompare(s: String, t: String): Boolean {
    var i = s.length - 1
    var j = t.length - 1
    var skipS = 0
    var skipT = 0
    /**
     * Here we use OR rather than AND because we continue processing
     * as long as either string still has characters to process, even if
     * one is longer or shorter than the other. We have to compare the
     * entire string after backspacing.
     *
     * Ex:
     * i reaches -1 (empty string), but j >= 0, but the remaining string
     * will be empty after backspacing.
     */
    while (i >= 0 || j >= 0) {
        // Backspace s
        while (i >= 0) {
            if (s[i] == '#') {
                skipS++
                i--
            } else if (skipS > 0) {
                // It's normal character and we have to backspace it.
                skipS--
                i--
            } else {
                // If it's not '#' and we dont' have any backspace, then we break the backspace loop.
                break
            }
        }

        // Backspace t
        while (j >= 0) {
            if (t[j] == '#') {
                skipT++
                j--
            } else if (skipT > 0) {
                skipT--
                j--
            } else {
                break
            }
        }

        // If the both strings are not empty, then compare two characters
        if (i >= 0 && j >= 0) {
            if (s[i] != t[j]) return false
        // If one of the strings is empty, then it's not equal
        } else if (i >= 0 || j >= 0) return false

        // The two characters are the same, so we move to the next iteration.
        i--
        j--
    }
    return true
}
  • Time Complexity: O(s + t).
  • Space Complexity: O(1).

Edge Cases

s t Result Reason
ab#c ad#c true ac → ✅ true
ab## c#d# true Both empty → ✅ true
a##c #a#c true Both c → ✅ true
ab#d ad true ad → ✅ true
ab##c #a#c true c → ✅ true
bxj##tw bxo#j##tw true btw → ✅ true
a#c b false c != b → ❌ false
a#c a false c != a → ❌ false
bxj##tw bxj###tw false s = btw, t = tw → j missing in t → ❌

Pitfalls

  • Using AND instead of OR in the main loop: Must use while (i >= 0 || j >= 0) to handle cases where one string is longer than the other.
  • Not handling multiple consecutive backspace characters: Need to count all # characters before processing the next character.
  • Forgetting to check if both strings are empty: After backspace operations, both strings might become empty, where i or j is 0.
  • Not resetting skip counters: The skip counter should be decremented for each character being skipped.

Similar or Follow-up Problems