Leetcode日记— 844. Backspace String Compare

碎碎念:昨天换了新电脑,装了一晚上环境,现在把昨天的博客补一下。

题目如下:

Given two strings S and T, return if they are equal when both are typed into empty text editors. # means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

Example 1:

Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".

Example 2:

Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".

Example3:

Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".

Example4:

Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".

思路

这道题主要的问题就是判断“#”对应的delete操作。

方法一:

最简单的思路就是把所有带“#”符号的地方前面按照规则delete掉,再开始对最终字符串进行比较。

那么如何使用合理的数据结构进行删除呢?我们想到,每一次都是第一次出现“#”号后删掉最近一个出现的字母。显然,这是一个标准的LIFO形式。那么我们可以用栈来对其进行实现。每当遍历到一个“#”以后,我们就把res栈的顶端pop出去。

代码如下:

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();
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/backspace-string-compare/solution/bi-jiao-han-tui-ge-de-zi-fu-chuan-by-leetcode-solu/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

方法二:

上面的方法显然空间复杂度为O(N+M),其中M和N分别为字符串长度。

那么我们可不可以把空间复杂度降到O(1)级别呢?

我们之前空间复杂度较高的原因是需要维护栈,而使用栈的原因是从前往后遍历,每次得到“退格”符号时都已经超过了要删去的字符。那么,既然如此,那我们不如直接从后往前遍历,这样每次出现“#”后的第一个字符就是要删去的。这样就不需要维护额外空间对其进行专门存储。

我们可以使用两个指针指向数组末尾,每次向字符串前方移动一格,若碰到了“#”则像前遍历时跳过对应“#”个数的格子。

代码如下:

class Solution {
    public boolean 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.charAt(i) == '#') {
                    skipS++;
                    i--;
                } else if (skipS > 0) {
                    skipS--;
                    i--;
                } else {
                    break;
                }
            }
            while (j >= 0) {
                if (T.charAt(j) == '#') {
                    skipT++;
                    j--;
                } else if (skipT > 0) {
                    skipT--;
                    j--;
                } else {
                    break;
                }
            }
            if (i >= 0 && j >= 0) {
// 两个指针一直移动,当skip为0的时候说明理论上该这俩相比,若不同则返回false
                if (S.charAt(i) != T.charAt(j)) {
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;
    }
}

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/backspace-string-compare/solution/bi-jiao-han-tui-ge-de-zi-fu-chuan-by-leetcode-solu/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注