Backspace String Compare — Two Pointer O(1) Space

Sanjeev SharmaSanjeev Sharma
1 min read

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

Sanjeev Sharma

Written by

Sanjeev Sharma

Full Stack Engineer · E-mopro