You're given two strings that represent text typed into a text editor. Each string may contain the special character #, which represents a backspace operation. When a backspace is encountered, it deletes the character immediately before it (if one exists).
Your task is to determine whether the two strings produce identical final text after all backspace operations have been applied.
Requirements
Process both strings considering backspace operations (represented by #)
Return true if the final processed strings are identical, false otherwise
Multiple consecutive backspaces should delete multiple characters
Backspaces at the beginning of a string have no effect (nothing to delete)
Optimize for space complexity if possible
Constraints
1 ≤ length of s, t ≤ 200
Strings contain only lowercase English letters and # characters
Try to solve this with O(1) extra space (not counting the output)
Expected time complexity: O(n + m) where n and m are the lengths of the strings
Examples
Example 1:
`
Input: s = "ab#c", t = "ad#c"
Output: true
Explanation:
s becomes "ac" (the 'b' is deleted by #)
t becomes "ac" (the 'd' is deleted by #)
Both final strings are "ac", so return true
`
Example 2:
`
Input: s = "ab##", t = "c#d#"
Output: true
Explanation:
s becomes "" (both 'a' and 'b' are deleted)
t becomes "" (both 'c' and 'd' are deleted)
Both are empty strings, so return true
`
Example 3:
`
Input: s = "a#c", t = "b"
Output: false
Explanation: