844. 比较含退格的字符串

🟢   🔖  栈 双指针 字符串 模拟  🔗 力扣 LeetCode

题目

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

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 = "b"

Output: false

Explanation: s becomes "c" while t becomes "b".

Constraints:

• 1 <= s.length, t.length <= 200
• s and t only contain lowercase letters and '#' characters.

Follow up: Can you solve it in O(n) time and O(1) space?

题目大意

给 2 个字符串，如果遇到 # 号字符，就回退一个字符。问最终的 2 个字符串是否完全一致。

解题思路

这一题可以用栈的思想来模拟：

• 遇到 # 字符就回退一个字符，注意 JS 中删除字符串的最后一个字符可以用 str.slice(0, -1)；
• 不是 # 号就入栈一个字符；
• 最后比较 2 个字符串即可；

代码

/**
 * @param {string} s
 * @param {string} t
 * @return {boolean}
 */
var backspaceCompare = function (s, t) {
	return backspace(s) === backspace(t);
};

var backspace = function (str) {
	let res = '';
	for (item of str) {
		if (item === '#') res = res.slice(0, -1);
		else res += item;
	}
	return res;
};

相关题目

题号	标题	题解	标签	难度
1598	文件夹操作日志搜集器		栈 数组 字符串
2390	从字符串中移除星号		栈 字符串 模拟