Compare two strings after interpreting # as a backspace character.
You are given two strings. Each string may contain lowercase letters and the # character. Treat # as a backspace: it deletes the character immediately before it, if one exists.
Return whether the two strings are equal after all backspaces are applied.
Input Format
- Two strings
sandt. - Each string consists of lowercase English letters and
#.
Output Format
- Return
trueif the two strings become identical after processing backspaces. - Otherwise, return
false.
Constraints
- The strings may be empty.
- A
#can remove a previous character only if one exists. - Aim for an time solution and or near-constant extra space if possible.
Example 1
Input
s = "ab#c", t = "ad#c"
Output
true
Explanation
After applying backspaces, both strings become "ac".
Example 2
Input
s = "ab##", t = "c#d#"
Output
true
Explanation
Both strings reduce to the empty string.
Show 1 more example
Example 3
Input
s = "a#c", t = "b"
Output
false
Explanation
The first string becomes "c", while the second remains "b".
Premium problem context
Unlock deeper context for this problem
Premium adds guided hints, editorial links, similar variants, discussion resources, and concept maps so you can understand why a problem matters, not just solve it once.