Given two strings
T, return if they are equal when both are typed into empty text editors.
# means a backspace character.
Note that after backspacing an empty text, the text will continue empty.
Input: S = "ab#c", T = "ad#c" Output: true Explanation: Both S and T become "ac".
Input: S = "ab##", T = "c#d#" Output: true Explanation: Both S and T become "".
Input: S = "a##c", T = "#a#c" Output: true Explanation: Both S and T become "c".
Input: S = "a#c", T = "b" Output: false Explanation: S becomes "c" while T becomes "b".
1 <= S.length <= 200
1 <= T.length <= 200
Tonly contain lowercase letters and
- Can you solve it in
use trie + backtracking
class Solution: def backspaceCompare(self, S: str, T: str) -> bool: def helper(s): result =  for c in s: if c != '#': result.append(c) elif result: result.pop() return "".join(result) return helper(S) == helper(T)
- Time Complexity: ~M + N
- Space Complexity: ~M + N
where M,N are the lengths of S and T respectively.