关注Java领域相关技术 记录有趣的事情

LeetCode-844. 比较含退格的字符串

US-B.Ralph
US-B.Ralph
2020-10-19

问题地址

LeetCode每日一题/2020-10-19

LeetCode844. 比较含退格的字符串

问题描述

规则

  • 给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。

注意：

  • 如果对空文本输入退格字符，文本继续为空。

示例

  • 示例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 <= 2001
  • 1 <= T.length <= 200
  • S 和 T 只含有小写字母以及字符 '#'

解析

解题思路

  • 遍历字符串S，将退格后的字符存入栈中；
  • 从后往前遍历字符串T，遍历过程中使用 wellNoCount 记录 # 出现的次数：
    • 若当前字符为 # ，则 wellNoCount+1 ；
    • 否则进行如下处理：
      • 当 wellNoCount 大于 0 时，wellNoCount - 1 ；
      • 当 wellNoCount 不大于0 时，且栈非空的情况下，比较当前字符与栈顶字符是否相同，不同则直接返回false；
    • 每次循环，以上操作结束后，若当前数组索引小于栈内元素个数，直接返回false；

数据操作分析

  • 见思路分析

复杂度分析

  1. 时间复杂度
  2. 空间复杂度

编码实现

public class LeetCode0844_BackspaceStringCompare1 {
    public boolean backspaceCompare(String S, String T) {
        Stack<Character> stack = new Stack<>();
        for (char sChar : S.toCharArray()) {
            if (sChar == '#' && !stack.isEmpty()) stack.pop();
            else if (sChar != '#') stack.push(sChar);
        }
        char[] tChars = T.toCharArray();
        int wellNoCount = 0;
        for (int i = tChars.length - 1; i >= 0; i--) {
            if (tChars[i] == '#') {
                wellNoCount++;
                continue;
            } else {
                if (wellNoCount > 0) wellNoCount--;
                else if (stack.isEmpty() || tChars[i] != stack.pop()) return false;
            }
            if (i < stack.size()) return false;
        }

        return true;
    }
}

官方解法

方法一 重构字符串

思路与算法：

  • 最容易想到的方法是将给定的字符串中的退格符和应当被删除的字符都去除，还原给定字符串的一般形式。然后直接比较两字符串是否相等即可。
  • 具体地，我们用栈处理遍历过程，每次我们遍历到一个字符：
    • 如果它是退格符，那么我们将栈顶弹出；
    • 如果它是普通字符，那么我们将其压入栈中。

复杂度分析：

  1. 时间复杂度:O(N+M)，其中 N 和 M 分别为字符串 S 和 T 的长度。我们需要遍历两字符串各一次。
  2. 空间复杂度：O(N+M)，其中 N 和 M 分别为字符串 S 和 T 的长度。主要为还原出的字符串的开销。

编码实现

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

方法二：双指针

思路及算法：

  • 一个字符是否会被删掉，只取决于该字符后面的退格符，而与该字符前面的退格符无关。因此当我们逆序地遍历字符串，就可以立即确定当前字符是否会被删掉。
  • 具体地，我们定义 \textit{skip} 表示当前待删除的字符的数量。每次我们遍历到一个字符：
    • 若该字符为退格符，则我们需要多删除一个普通字符，我们让 \textit{skip} 加 1；
    • 若该字符为普通字符：
      • 若 \textit{skip} 为 0，则说明当前字符不需要删去；
      • 若 \textit{skip} 不为 0，则说明当前字符需要删去，我们让 \textit{skip} 减 1。
  • 这样，我们定义两个指针，分别指向两字符串的末尾。每次我们让两指针逆序地遍历两字符串，直到两字符串能够各自确定一个字符，然后将这两个字符进行比较。重复这一过程直到找到的两个字符不相等，或遍历完字符串为止。

复杂度分析：

  1. 时间复杂度:O(N+M)，其中 N 和 M 分别为字符串 S 和 T 的长度。我们需要遍历两字符串各一次。
  2. 空间复杂度：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) {
                if (S.charAt(i) != T.charAt(j)) {
                    return false;
                }
            } else {
                if (i >= 0 || j >= 0) {
                    return false;
                }
            }
            i--;
            j--;
        }
        return true;
    }
}

精彩评论

跳转地址1：844【栈模拟】与【空间更优的双指针】详解

普通方法栈思路

这道题目一看就是要使用栈的节奏，这种匹配（消除）问题也是栈的擅长所在，跟着一起刷题的同学应该知道，在栈与队列：匹配问题都是栈的强项，我就已经提过了一次使用栈来做类似的事情了。

那么本题，确实可以使用栈的思路，但是没有必要使用栈，因为最后比较的时候还要比较栈里的元素，有点麻烦。

这里直接使用字符串string，来作为栈，末尾添加和弹出，string都有相应的接口，最后比较的时候，只要比较两个字符串就可以了，比比较栈里的元素方便一些。

复杂度分析：
  1. 时间复杂度:O(n + m)， n为S的长度，m为T的长度 ，也可以理解是O(n)的时间复杂度

  2. 空间复杂度：O(n + m)。对于每个字符串，我们只需要定义一个指针和一个计数器即可。

编码实现
class Solution {
public:
    bool backspaceCompare(string S, string T) {
        string s; // 当栈来用
        string t; // 当栈来用
        for (int i = 0; i < S.size(); i++) {
            if (S[i] != '#') s += S[i];
            else if (!s.empty()){
                s.pop_back();
            }
        }
        for (int i = 0; i < T.size(); i++) {
            if (T[i] != '#') t += T[i];
            else if (!t.empty()) {
                t.pop_back();
            }
        }
        if (s == t) return true; // 直接比较两个字符串是否相等，比用栈来比较方便多了
        return false;
    }
};
  • 当然以上代码，大家可以发现有重复的逻辑处理S，处理T，可以把这块公共逻辑抽离出来，代码精简
class Solution {
private:
string getString(const string& S) {
    string s;
    for (int i = 0; i < S.size(); i++) {
        if (S[i] != '#') s += S[i];
        else if (!s.empty()) {
            s.pop_back();
        }
    }
    return s;
}
public:
    bool backspaceCompare(string S, string T) {
        return getString(S) == getString(T);
    }
};

优化方法（从后向前双指针）

当然还可以有使用 O(1) 的空间复杂度来解决该问题。

同时从后向前遍历S和T（i初始为S末尾，j初始为T末尾），记录#的数量，模拟消除的操作，如果#用完了，就开始比较S[i]和S[j]。

如果S[i]和S[j]不相同返回false，如果有一个指针（i或者j）先走到的字符串头部位置，也返回false。

复杂度分析：

  1. 时间复杂度:O(n + m)， n为S的长度，m为T的长度 ，也可以理解是O(n)的时间复杂度

  2. 空间复杂度：O(1)。

编码实现
class Solution {
public:
    bool backspaceCompare(string S, string T) {
        int sSkipNum = 0; // 记录S的#数量
        int tSkipNum = 0; // 记录T的#数量
        int i = S.size() - 1;
        int j = T.size() - 1;
        while (1) {
            while (i >= 0) { // 从后向前，消除S的#
                if (S[i] == '#') sSkipNum++;
                else {
                    if (sSkipNum > 0) sSkipNum--;
                    else break;
                }
                i--;
            }
            while (j >= 0) { // 从后向前，消除T的#
                if (T[j] == '#') tSkipNum++;
                else {
                    if (tSkipNum > 0) tSkipNum--;
                    else break;
                }
                j--;
            }
            // 后半部分#消除完了，接下来比较S[i] != T[j]
            if (i < 0 || j < 0) break; // S 或者T 遍历到头了
            if (S[i] != T[j]) return false;
            i--;j--;
        }
        // 说明S和T同时遍历完毕
        if (i == -1 && j == -1) return true;
        return false;
    }
};
US-B.Ralph
LeetCode数据结构与算法算法

Leave a Comment

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

13 − 9 =