欢迎大家访问我的GitHub博客
https://lunan0320.cn
文章目录844. 比较含退格的字符串(Leetcode刷题笔记)
题目解题代码 C++(核心代码)解题代码 C++(本地编译运行)算法效率
题目给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，请你判断二者是否相等。# 代表退格字符。
如果相等，返回 true ；否则，返回 false 。
注意：如果对空文本输入退格字符，文本继续为空。
示例 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 = “#a#c”
输出：true
解释：s 和 t 都会变成 “c”。
示例 4：
输入：s = “a#c”, t = “b”
输出：false
解释：s 会变成 “c”，但 t 仍然是 “b”。
解题思路： 此处学会使用栈的处理方式，而且是用容器的push_back()以及pop_back()的方法
如果不是退格就入栈，如果是退格且不为空的情况就出栈
class Solution {
public:
bool backspaceCompare(string s, string t) {
return rebuild(s) == rebuild(t);
}
string rebuild(string m){
int len = m.size();
string res;
for(int i = 0;i < len; i++){
if(m[i] != '#'=){
res.push_back(m[i]);
}else if (!res.empty()){
res.pop_back();
}
}
return res;
}
};
解题代码 C++(本地编译运行)
// head.h #pragma once #include#include #include using namespace std;
// Solution3.h
#include "head.h"
//退格
class Solution3 {
public:
bool backspaceCompare(string s, string t) {
return rebuild(s) == rebuild(t);
}
string rebuild(string m) {
int len = m.size();
string res;
for (int i = 0; i < len; i++) {
if (m[i] != '#') {
res.push_back(m[i]);
}
else if (!res.empty()) {
res.pop_back();
}
}
return res;
}
};
// main.cpp
#include "Solution2.h"
int main() {
Solution3 solution;
string s = "ab#c";
string t = "ad#c";
bool res=solution.backspaceCompare(s, t);
cout << res << endl;
}
算法效率
执行用时： 0 ms , 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：6.1 MB , 在所有 C++ 提交中击败了58.10% 的用户
