129. Backspace Showdown
Two people type on a keyboard where the # character means a backspace: it deletes the letter just before it, and does nothing when there is no letter to delete. The typed keystrokes are recorded in the strings s and t, which contain lower case letters and #.
Return true if the two screens show exactly the same text after all keystrokes were applied, and false otherwise. Both results may be empty. A stack gives a simple solution with extra memory; try to do it with two pointers that scan both strings from the right using constant extra memory.
Example 1
- Input:
- s = "rs#t", t = "ru#t"
- Output:
- true
- Explanation:
Both strings end up on the screen as rt, so the answer is true.
Example 2
- Input:
- s = "pq#r", t = "pr#q"
- Output:
- false
- Explanation:
The first screen shows pr and the second one shows pq, so they differ.
Constraints
1 ≤ s.length, t.length ≤ 2 * 105
s and t contain only lower case letters and #
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
Expected complexity
- Time
- O(n + m)
- Space
- O(1)