Backspace String Compare — Two Pointer O(1) Space
Advertisement
Problem 256 · Backspace String Compare
Difficulty: Easy · Pattern: Two Pointer from Right
Solutions
# Python — O(1) space two pointer
def backspaceCompare(s, t):
i, j = len(s)-1, len(t)-1
skip_s = skip_t = 0
while i >= 0 or j >= 0:
while i >= 0:
if s[i] == '#': skip_s += 1; i -= 1
elif skip_s > 0: skip_s -= 1; i -= 1
else: break
while j >= 0:
if t[j] == '#': skip_t += 1; j -= 1
elif skip_t > 0: skip_t -= 1; j -= 1
else: break
if i >= 0 and j >= 0 and s[i] != t[j]: return False
if (i >= 0) != (j >= 0): return False
i -= 1; j -= 1
return True
// Java
public boolean backspaceCompare(String s, String t) {
int i=s.length()-1, j=t.length()-1, ss=0, ts=0;
while (i>=0 || j>=0) {
while (i>=0) { if(s.charAt(i)=='#'){ss++;i--;} else if(ss>0){ss--;i--;} else break; }
while (j>=0) { if(t.charAt(j)=='#'){ts++;j--;} else if(ts>0){ts--;j--;} else break; }
if (i>=0 && j>=0 && s.charAt(i)!=t.charAt(j)) return false;
if ((i>=0)!=(j>=0)) return false;
i--; j--;
}
return true;
}
Complexity
- Time: O(n+m)
- Space: O(1)
Advertisement