844. 比较含退格的字符串

问题844 比较含退格的字符串 ★☆☆☆☆

https://leetcode-cn.com/problems/backspace-string-compare/

这个题目最直接的思路就是按照backspace规则，分别把两个字符串做backspace处理，然后比较得到的结果。代码并不复杂，提交以后也通过了。这种处理的时间复杂度和空间复杂度都是O(N).

那么题目中附加的能不能以O(1)的空间复杂度解答这个题目呢？参考了官方题解才恍然大悟，backspace只可能影响左边的字符，所以倒序处理字符串，就能增量的挨个比较下一个能保留下来的字符。换句话说，我们倒序遍历两个字符串，每次遍历的目标是获得下一个能保留下来的字符的下标，然后比较两个字符串下一个能保留下来的字符是否相同，相同则继续下一轮遍历，不同或有一方为空了，那么说明两个字符串backspace后的字符串不同。

	public boolean backspaceCompare(String s, String t) {
		char[] schars = s.toCharArray();
		char[] tchars = t.toCharArray();

		int i = schars.length, j = tchars.length;
		while (true) {
			i = idxOfNextRightMostChar(schars, i);
			j = idxOfNextRightMostChar(tchars, j);
			if (i == -1 && j == -1) {
				return true;
			} else if (i != -1 && j != -1) {
				char ch1 = schars[i];
				char ch2 = tchars[j];
				if (ch1 != ch2) {
					return false;
				}
			} else {
				return false;
			}
		}
	}

	private int idxOfNextRightMostChar(char[] chars, int idx) {
		int skip = 0;

		for (int i = --idx; i >= 0; i--) {
			char ch = chars[i];
			if (ch == '#') {
				skip++;
			} else {
				if (skip > 0) {
					skip--;
				} else {
					return i;
				}
			}
		}

		return -1;
	}

在 LeetCode 查看