public boolean backspaceCompare(String S, String T) {

int lenS = S.length();

int lenT = T.length();

int indexS = lenS-1;

int countS = 0;

int indexT = lenT-1;

int countT = 0;

while (indexS >= 0 && indexT >= 0) {

char charS = S.charAt(indexS);

char charT = T.charAt(indexT);

if (charS != '#' && charT != '#' && countS == 0 && countT == 0) {

if (charS != charT) return false;

indexS--;

indexT--;

} else {

if (charS == '#') {

countS++;

indexS--;

} else {

if (countS != 0) {

countS--;

indexS--;

}

}

if (charT == '#') {

countT++;

indexT--;

} else {

if (countT != 0) {

countT--;

indexT--;

}

}

}

}

while (indexS >= 0) {

if (S.charAt(indexS) == '#') {

countS++;

} else {

if (countS == 0) return false;

countS--;

}

indexS--;

}

while (indexT >= 0) {

if (T.charAt(indexT) == '#') {

countT++;

} else {

if (countT == 0) return false;

countT--;

}

indexT--;

}

return true;

}

/**

public boolean backspaceCompare2(String S, String T) {

return build(S).equals(build(T));

}

public String build(String S) {

Stack<Character> ans = new Stack();

for (char c: S.toCharArray()) {

if (c != '#')

ans.push(c);

else if (!ans.empty())

ans.pop();

}

return String.valueOf(ans);

}

/**

public boolean backspaceCompare3(String S, String T) {

int i = S.length() - 1, j = T.length() - 1;

int skipS = 0, skipT = 0;

while (i >= 0 || j >= 0) { // While there may be chars in build(S) or build (T)

while (i >= 0) { // Find position of next possible char in build(S)

if (S.charAt(i) == '#') {skipS++; i--;}

else if (skipS > 0) {skipS--; i--;}

else break;

}

while (j >= 0) { // Find position of next possible char in build(T)

if (T.charAt(j) == '#') {skipT++; j--;}

else if (skipT > 0) {skipT--; j--;}

else break;

}

// If two actual characters are different

if (i >= 0 && j >= 0 && S.charAt(i) != T.charAt(j))

return false;

// If expecting to compare char vs nothing

if ((i >= 0) != (j >= 0))

return false;

i--; j--;

}

return true;

}