844. Backspace String Compare

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Example 1:

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Example 2:

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Example 3:

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Example 4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

Note:

1. 1 <= S.length <= 200
2. 1 <= T.length <= 200
3. S and T only contain lowercase letters and '#' characters.

Follow up:

• Can you solve it in O(N) time and O(1) space?

---

给定两个字符串，其中包含小写字母和#，#表示删除前一个字符。问这两个字符串的最终结果是否一致。

这道题如果不考虑Follow up的话很简单，新建一个string，看到字母就push_back，看到#就pop_back，最后看剩余字符串是否相等即可。

但是Follow up要求只使用O(1)的空间，这就需要思考一下了。思路是这样的，从后往前处理两个字符串，统计#的数目，模拟删除过程，直到无法删除找到一个能被留在最终字符串中的字母，比较S和T的这个字符是否相等。完整代码如下：

class Solution {
public:
	bool backspaceCompare(string S, string T) {
		int i = S.size() - 1, j = T.size() - 1;
		while (i >= 0 || j >= 0) {
			int skipS = 0, skipT = 0;
			while (i >= 0) {
				if (S[i] == '#') {
					++skipS;
					--i;
				}
				else if (skipS > 0) {
					--skipS;
					--i;
				}
				else {
					break;
				}
			}

			while (j >= 0) {
				if (T[j] == '#') {
					++skipT;
					--j;
				}
				else if (skipT > 0) {
					--skipT;
					--j;
				}
				else {
					break;
				}
			}

			if ((i >= 0) != (j >= 0))return false;
			if (i >= 0 && S[i] != T[j])return false;
			--i;
			--j;
		}
		return true;
	}
};

本代码提交AC，用时0MS。