Description
https://leetcode.com/problems/backspace-string-compare/
Given two strings S
and 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.
Example 1:
Input: S = "ab#c", T = "ad#c" Output: true Explanation: Both S and T become "ac".
Example 2:
Input: S = "ab##", T = "c#d#" Output: true Explanation: Both S and T become "".
Example 3:
Input: S = "a##c", T = "#a#c" Output: true Explanation: Both S and T become "c".
Example 4:
Input: S = "a#c", T = "b" Output: false Explanation: S becomes "c" while T becomes "b".
Note:
1 <= S.length <= 200
1 <= T.length <= 200
S
andT
only contain lowercase letters and'#'
characters.
Follow up:
- Can you solve it in
O(N)
time andO(1)
space?
Explanation
use trie + backtracking
Python Solution
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.