【算法千题案例】每日LeetCode打卡——102.比较含退格的字符串

@TOC

📢前言

• 🌲 每天打卡一道算法题，既是一个学习过程，又是一个分享的过程😜
• 🌲 提示：本专栏解题 编程语言一律使用 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 两种编程语言进行解题
• 一些方法也是参考力扣大神写的，也是边学习边分享，再次感谢算法大佬们
• 那今天的算法题分享到此结束啦，明天再见！