LeetCode C++ 844. Backspace String Compare【StringStackTwo Pointers】简单

Given two strings S and T, return 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 = "#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 <= S.length <= 2001 <= T.length <= 200S and T only contain lowercase letters and '#' characters.

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

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

---

解法1 暴力方法

如果没有其它思路的话，可能想到的就是暴力。对原始字符串，如果一个字符是 # ，就将它前一个字符（如果存在的话）和 # 一起删去，然后检查下一个字符。最终整理得到真正的文本串，进行比较。在原始字符串之上进行这些操作，时间复杂度是 $O(n^2)$ 级别，意义不大，因而此处不讨论具体代码的实现。

---

解法2 额外的字符串空间

如果使用额外的字符串空间，可以将暴力方法的复杂度降低到 $O(n)$ 时间、$O(n)$ 空间，具体代码很简单：

class Solution { public: bool backspaceCompare(string s, string t) { string st, tt; for (const char &c : s) { if (c != '#') st.push_back(c); else if (!st.empty()) st.pop_back(); } for (const char &c : t) { if (c != '#') tt.push_back(c); else if (!tt.empty()) tt.pop_back(); } return st == tt; } };

运行结果如下：

执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户 内存消耗：6.4 MB, 在所有 C++ 提交中击败了41.17% 的用户

不过这种后进先出的删除方法让人想到了栈，因此另一种写法如下：

class Solution { private: string convertToNormalText(const string &s) { string textStack; for (const char &c : s) { if (c != '#') textStack.push_back(c); else if (!textStack.empty()) textStack.pop_back(); } return textStack; } public: bool backspaceCompare(string s, string t) { string&& sstack = convertToNormalText(s); string&& tstack = convertToNormalText(t); return sstack == tstack; } };

效率几乎一样：

执行用时：0 ms, 在所有 C++ 提交中击败了100.00% 的用户 内存消耗：6.4 MB, 在所有 C++ 提交中击败了41.17% 的用户

---

解法3 双指针

使用双指针的方法，可以将空间复杂度降低到 $O(1)$ 。对于两个字符串，如果从前往后比较，需要考虑到 # 的影响，比较麻烦。因此使用从后往前比较的做法。即使这样也要注意，这题有很多细节要仔细考虑，不然很容易出错。具体步骤如下：

我们维护两个计数器 backOfS, backOfT 和两个指针 sright, tright ，计数器记录退格的个数，指针分别指向两个字符串的尾部。然后倒序遍历字符串，决定当前字符是否需要跳过，从而将两个指针分别指向对应字符串的有效字符； 遇到 # 时，将对应的计数器 + 1 ，遍历指针往前移一位从而跳过该字符；遇到非 # 字符时，会有如下的判断： 如果退格计数器为 0 ，那么该字符无法跳过，属于有效字符；如果退格计数器 >= 0 ，那么该字符需要跳过，所以需要让计数器 - 1 ，同时让遍历指针往前移一位； 经过这一过程，此时两个指针都指向有效字符，然后进行比较。相等则重复遍历过程；如果发现两个位置上的有效字符并不相同，或者其中一个字符串已经遍历完，那么直接返回 false ，否则继续往前遍历剩下的字符；最后，如果两个字符串都已经遍历完，可知两者经过退格操作后是相等的字符串，返回 true ；时间复杂度是 $O(N)$ ，空间复杂度是 $O(1)$ 。 class Solution { private: //跳跃过退格和无效字符,到下一个有效字符 void jumpBackspace(const string &s, int &i, int &b) { while (i >= 0) { if (s[i] == '#') ++b; //计算退格 else if (b) --b; //不是退格但存在退格,因此不是有效字符 else break; //不是退格,不存在退格,是有效字符,返回 --i; //是退格并计算;不是退格但存在退格---->都不是有效字符 } } public: bool backspaceCompare(string s, string t) { //双指针,从后往前扫描 int sright = s.size() - 1, tright = t.size() - 1; int backOfS = 0, backOfT = 0; while (sright >= 0 || tright >= 0) { jumpBackspace(s, sright, backOfS); jumpBackspace(t, tright, backOfT); if (sright < 0 || tright < 0) break; //判断是否超出范围 if (s[sright--] != t[tright--]) return false; //有效字符比较,不相等则返回false } return sright < 0 && tright < 0; } };

效率如下，虽然好像更低了，但是对于字符串 s, t 十分庞大、内存无法装入的情况而言，更有用处：

执行用时：4 ms, 在所有 C++ 提交中击败了51.14% 的用户 内存消耗：6.3 MB, 在所有 C++ 提交中击败了70.90% 的用户