【算法千题案例】每日一练LeetCode打卡——102.比较含退格的字符串
【算法千题案例】每日一练LeetCode打卡——102.比较含退格的字符串
呆呆敲代码的小Y
发布于 2022-01-24 10:08:45
发布于 2022-01-24 10:08:45
请添加图片描述
前言
算法题 |
|---|
- 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程
- 提示：本专栏解题 编程语言一律使用 C# 和 Java 两种进行解题
- 要保持一个每天都在学习的状态，让我们一起努力成为算法大神吧！
- 今天是力扣算法题持续打卡第102天！
算法题 |
|---|
原题样例：比较含退格的字符串
给定 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”。提示：
- 1 <= s.length, t.length <= 200
- s 和 t 只含有小写字母以及字符 ‘#’
C#方法：重构字符串
将给定的字符串中的退格符和应当被删除的字符都去除，还原给定字符串的一般形式。
然后直接比较两字符串是否相等即可。
用 栈 处理遍历过程，每次我们遍历到一个字符：
- 如果它是退格符，那么我们将栈顶弹出；
- 如果它是普通字符，那么我们将其压入栈中。
代码：
public class Solution {
public bool BackspaceCompare(string s, string t) {
Stack<char> stackS = new Stack<char>();
Stack<char> stackT = new Stack<char>();
int n1 = s.Length;
int n2 = t.Length;
for (int i = 0; i < n1; ++i) {
if (s[i] == '#') {
if (stackS.Count == 0) continue;
stackS.Pop();
} else {
stackS.Push(s[i]);
}
}
for (int i = 0; i < n2; ++i) {
if (t[i] == '#') {
if (stackT.Count == 0) continue;
stackT.Pop();
} else {
stackT.Push(t[i]);
}
}
if (stackS.Count != stackT.Count) return false;
while (stackS.Count != 0) {
if (stackS.Pop() != stackT.Pop()) return false;
}
return true;
}
}执行结果
通过
执行用时：76 ms，在所有 C# 提交中击败了71.14%的用户
内存消耗：37.9 MB，在所有 C# 提交中击败了10.70%的用户Java 方法：重构字符串
思路解析 将给定的字符串中的退格符和应当被删除的字符都去除，还原给定字符串的一般形式。
然后直接比较两字符串是否相等即可。
用 栈 处理遍历过程，每次我们遍历到一个字符：
- 如果它是退格符，那么我们将栈顶弹出；
- 如果它是普通字符，那么我们将其压入栈中。
代码：
class Solution {
public boolean backspaceCompare(String S, String T) {
return build(S).equals(build(T));
}
public String build(String str) {
StringBuffer ret = new StringBuffer();
int length = str.length();
for (int i = 0; i < length; ++i) {
char ch = str.charAt(i);
if (ch != '#') {
ret.append(ch);
} else {
if (ret.length() > 0) {
ret.deleteCharAt(ret.length() - 1);
}
}
}
return ret.toString();
}
}执行结果
通过
执行用时：1 ms，在所有 Java 提交中击败了59.41%的用户
内存消耗：36.4 MB，在所有 Java 提交中击败了7.53%的用户复杂度分析
时间复杂度：O(N+M)，其中 N 和 M 分别为字符串 S 和 T 的长度
空间复杂度：O(N+M)，其中 N 和 M 分别为字符串 S 和 T 的长度总结
- 今天是力扣算法题打卡的第102天！
- 文章采用
C#和Java两种编程语言进行解题 - 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
- 那今天的算法题分享到此结束啦，明天再见！
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022/01/21 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
