当前位置:网站首页>2022-7-7 Leetcode 844. Compare strings with backspace
2022-7-7 Leetcode 844. Compare strings with backspace
2022-07-07 13:39:00 【weixin_ fifty-one million one hundred and eighty-seven thousand】
Method 1 : Stack
class Solution {
public:
bool backspaceCompare(string s, string t) {
string tmps = "", tmpt = "";
for (auto& ch:s){
if (ch == '#'){
if (!tmps.empty())
tmps.pop_back();
}else tmps.push_back(ch);
}
for (auto& ch:t){
if (ch == '#'){
if (!tmpt.empty())
tmpt.pop_back();
}else tmpt.push_back(ch);
}
return tmps == tmpt;
}
};
Method 2 : Double pointer
class Solution {
public:
bool backspaceCompare(string S, string T) {
int i = S.length() - 1, j = T.length() - 1;
int skipS = 0, skipT = 0;
while (i >= 0 || j >= 0) {
while (i >= 0) {
if (S[i] == '#') {
skipS++, i--;
} else if (skipS > 0) {
skipS--, i--;
} else {
break;
}
}
while (j >= 0) {
if (T[j] == '#') {
skipT++, j--;
} else if (skipT > 0) {
skipT--, j--;
} else {
break;
}
}
if (i >= 0 && j >= 0) {
if (S[i] != T[j]) {
return false;
}
} else {
if (i >= 0 || j >= 0) {
return false;
}
}
i--, j--;
}
return true;
}
};
author :demigodliu
link :https://leetcode.cn/problems/backspace-string-compare/solution/shuang-zhi-zhen-bi-jiao-han-tui-ge-de-zi-8fn8/
source : Power button (LeetCode)
The copyright belongs to the author . Commercial reprint please contact the author for authorization , Non-commercial reprint please indicate the source .
边栏推荐
猜你喜欢
随机推荐
Navicat运行sql文件导入数据不全或导入失败
Digital IC Design SPI
Write it down once Net a new energy system thread surge analysis
靠卖概念上市,认养一头牛能走多远?
Read PG in data warehouse in one article_ stat
Some principles of mongodb optimization
[daily training] 648 Word replacement
1. Deep copy 2. Call apply bind 3. For of in differences
我那“不好惹”的00后下属:不差钱,怼领导,抵制加班
Ikvm of toolbox Net project new progress
Scripy tutorial classic practice [New Concept English]
RealBasicVSR测试图片、视频
Sliding rail stepping motor commissioning (national ocean vehicle competition) (STM32 master control)
[learning notes] agc010
室内ROS机器人导航调试记录(膨胀半径的选取经验)
xshell连接服务器把密钥登陆改为密码登陆
MongoDB 分片总结
Read PG in data warehouse in one article_ stat
LED light of single chip microcomputer learning notes
Build a secure and trusted computing platform based on Kunpeng's native security