844. Backspace String Compare

Given two strings s and t, return true 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.

辅助方法getNextValid，返回下一个有效值。
将两个指针分别设置在两个字符串的尾部。
当两指针有一个大于0时，进行循环。
每次都搜索两个指针的下一个有效值。
如果两个指针上的字符不同则返回false。

最后返回两个指针的停留位置是否相同。

注意：
如果有一个字符串指针先更新到0以下，另一个指针仍有可能更新到一个“#”字符位置。
此时最后的结应该是两个空字符串。
因此需要继续循环一次，得出其是否会归到零以下。如果此时归零则两者的指针位置仍然相等。

因此即使getNextValid返回的下一个值为负数也应该保留其数值。

class Solution {
    public boolean backspaceCompare(String s, String t) {
        int i = s.length()-1;
        int j = t.length()-1;

        while(i >= 0 || j >= 0){
            i = getNextValid(s, i);
            j = getNextValid(t, j);
            if( i >= 0 && j >= 0 && s.charAt(i) != t.charAt(j)){    
                return false;
            }
            i--;
            j--;
        }
        return (i == j);
    }
    
    private int getNextValid(String s, int start){
        int i = start;
        int count = 0;
        while(i >= 0 && (s.charAt(i) == '#' || count != 0)){
            if(s.charAt(i) == '#'){
                count++;
            }
            else{
                count--;
            }
            i--;
        }
        return i;
    }
}