比较退格的字符串（844）

题目

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

示例

输入：S = "ab#c", T = "ad#c" 输出：true

输入：S = "ab##", T = "c#d#" 输出：true

输入：S = "a##c",T = "#a#c" 输出：true

输入：S = "a#c", T = "b" 输出：false

提示

1 <= S.length <= 200 1 <= T.length <= 200 S 和 T 只含有小写字母以及字符 '#'。

算法

栈

将字符串转化为数组，遍历数组，遇到"#"弹出栈顶元素，如果不是"#"推入栈中

export const backspaceCompare_1 = (S, T) => {
	let arr1 = [],
		arr2 = [];
	const str1 = backspace(arr1, S);
	const str2 = backspace(arr2, T);
	return str1 === str2;

	function backspace(arr, str) {
		for (let i = 0; i < str.length; i++) {
			if (str[i] !== "#") {
				arr.push(str[i]);
			} else {
				if (arr.length > 0) {
					arr.pop();
				}
			}
		}
		return arr.join();
	}
};

双指针

设置双指针，分别指向两字符串尾部，向前遍历，遇到"#"则跳过之前的字符（保存一个变量skip为连续出现的"#"的次数），比较两个指针指向的字符

注意：每次需要判断是否有一个指针已经指向字符串头部而另一个指针没有结束字符串遍历，此时返回false

export const backspaceCompare_2 = (S, T) => {
	let l = S.length - 1,
		r = T.length - 1;
	let s_skip = 0,
		t_skip = 0;
	while (l >= 0 || r >= 0) {
		while (l >= 0) {
			if (S[l] === "#") {
				s_skip++;
				l--;
			} else if (s_skip > 0) {
				s_skip--;
				l--;
			} else {
				break;
			}
		}
		while (r >= 0) {
			if (T[r] === "#") {
				t_skip++;
				r--;
			} else if (t_skip > 0) {
				t_skip--;
				r--;
			} else {
				break;
			}
		}
		if (l >= 0 && r >= 0) {
			if (S[l] !== T[r]) {
				return false;
			}
		}
		if ((r < 0 && l >= 0) || (r >= 0 && l < 0)) {
			return false;
		}
		l--;
		r--;
	}
	return true;
};