wordpress指定分類名稱知乎關(guān)鍵詞排名優(yōu)化
每日一題(LeetCode)----數(shù)組–移除元素（四）
1.題目（[844. 比較含退格的字符串](https://leetcode.cn/problems/sqrtx/)）
給定 s 和 t 兩個字符串，當(dāng)它們分別被輸入到空白的文本編輯器后，如果兩者相等，返回 true 。# 代表退格字符。
**注意：**如果對空文本輸入退格字符，文本繼續(xù)為空。
示例 1：
輸入：s = "ab#c", t = "ad#c"
輸出：true
解釋：s 和 t 都會變成 "ac"。
示例 2：
輸入：s = "ab##", t = "c#d#"
輸出：true
解釋：s 和 t 都會變成 ""。
示例 3：
輸入：s = "a#c", t = "b"
輸出：false
解釋：s 會變成 "c"，但 t 仍然是 "b"。
提示：
1 <= s.length, t.length <= 200s和t只含有小寫字母以及字符'#'
進(jìn)階：
- 你可以用
O(n)的時間復(fù)雜度和O(1)的空間復(fù)雜度解決該問題嗎？
2.解題思路
思路一： 重構(gòu)字符串（單指針）
1.先將兩個字符串中的退格字符和應(yīng)該被刪除的字符去除掉
我們用一個變量來存已經(jīng)遍歷到的退格字符的數(shù)量
然后我們從后向前遍歷這兩個字符串
如果遍歷到的是退格字符，那么刪除退格字符，然后記錄已經(jīng)遍歷到退格字符的數(shù)量的變量進(jìn)行加一操作
如果遍歷到的是字符，那我們看記錄已經(jīng)遍歷到退格字符的數(shù)量的變量是否大于0
如果大于0刪除當(dāng)前遍歷到的字符，記錄已經(jīng)遍歷到退格字符的數(shù)量的變量進(jìn)行減一操作
如果小于0，那么不進(jìn)行操作，進(jìn)行向前遍歷
2.然后將兩個字符串進(jìn)行比較
思路二： 重構(gòu)字符串（棧）
最容易想到的方法是將給定的字符串中的退格符和應(yīng)當(dāng)被刪除的字符都去除，還原給定字符串的一般形式。然后直接比較兩字符串是否相等即可。
具體地，我們用棧處理遍歷過程，每次我們遍歷到一個字符：
如果它是退格符，那么我們將棧頂彈出；
如果它是普通字符，那么我們將其壓入棧中。
原作者：力扣官方題解
鏈接：https://leetcode.cn/problems/backspace-string-compare/
3.寫出代碼
思路一的代碼：
class Solution {
public:bool backspaceCompare(string s, string t) {int length1 = s.size();int length2 = t.size();int sum1 = 0;int sum2 = 0;for (int i = length1 - 1; i >= 0; i--) {if (s.size() == 0) {break;}if (s[i] == '#') {s.erase(i, 1);sum1++;}else {if (sum1 > 0) {s.erase(i, 1);sum1--;}}}for (int i = length2 - 1; i >= 0; i--) {if (t.size() == 0) {break;}if (t[i] == '#') {t.erase(i, 1);sum2++;}else {if (sum2 > 0) {t.erase(i, 1);sum2--;}}}//進(jìn)行比較if (s == t) {return true;}else {return false;}}
};
思路二的代碼：
class Solution {
public:bool backspaceCompare(string S, string T) {return build(S) == build(T);}string build(string str) {string ret;for (char ch : str) {if (ch != '#') {ret.push_back(ch);} else if (!ret.empty()) {ret.pop_back();}}return ret;}
};