backspace-string-compare
Last updated
Was this helpful?
Last updated
Was this helpful?
In this solution, we build a new string after backspace.
From left to right, if curr char != '#', append to newString.
If curr char == '#', check newString is null?
if newString is null, do nothing, continue
if newString is not null, delete last char.
return newString.
Compare new build string from S and T.
For example:
Time Complexity: O(N + M)
Space Complexity: O(N + M)
N - length of String S
M - length of String T
This solution is to compare char on the fly.
Scan both String S and T from right to left
Define '#' count and index: sIdx, tIdx, if encounter '#', count++, else count--.
Until count = 0, and curr char != '#', check current position char
if out of string(S/T) index, then s = *, t = *
else s = S.charAt(sIdx), t = T.charAt(tIdx)
compare current s == t?
if s != t
, return false
else continue
If complete loop S and T, return true.
for example:
Time Complexity: O(N + M)
Space Complexity: O(1)
N - length of String S
M - length of String T