# 844 - Backspace String Compare

## 解法一 - Two Pointer

S = "xyyy###z" T = "xz"

1. 兩邊的 char 不相同
2. 一邊已經走到底，另一邊還沒走到底

``````class Solution {
public:
bool backspaceCompare(string S, string T) {
int indexS=S.length()-1, indexT=T.length()-1;

while(indexS >= 0 || indexT >= 0) {
int idxS = findValidIndex(S, indexS);
int idxT = findValidIndex(T, indexT);

if(idxS < 0 && idxT < 0)
return true;
else if(idxS < 0 || idxT < 0)
return false;
else if(S[idxS] != T[idxT])
return false;

indexS = idxS-1;
indexT = idxT-1;
}

return true;
}

private:
int findValidIndex(string str, int index) {
if(str[index] != '#')
return index;
else {
int bscount = 0;

while(index >= 0 && str[index] == '#') {
bscount++;
index--;
}

return index-bscount;
}
}
};
``````

``````class Solution {
public:
bool backspaceCompare(string S, string T) {
int indexS=S.length()-1, indexT=T.length()-1;

while(indexS >= 0 || indexT >= 0) {
int idxS = findValidIndex(S, indexS);
int idxT = findValidIndex(T, indexT);

if(idxS < 0 && idxT < 0)
return true;
else if(idxS < 0 || idxT < 0)
return false;
else if(S[idxS] != T[idxT])
return false;

indexS = idxS-1;
indexT = idxT-1;
}

return true;
}

private:
int findValidIndex(string str, int index) {
int bscount = 0;
while(index >= 0) {
if(str[index] == '#') {
bscount++;
index--;
}
else if(bscount > 0) { // index point to non-bs char, but already have bs
bscount--;
index--;
}
else if(bscount == 0){ // index point to non-bs character
break;
}
}

return index;
}
};
``````