leetcode刷题 844. 比较含退格的字符串，Easy （Java）栈+双指针

1.题目描述2.解法

2.1 栈

2.1.1 思路2.1.2 Java代码 2.2 双指针

2.2.1 思路2.2.2 Java代码

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。

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

示例 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 = “b”
输出： false
解释： s 会变成 “c”，但 t 仍然是 “b”。

提示：

1 <= s.length, t.length <= 200s 和 t 只含有小写字母以及字符 ‘#’

进阶：

你可以用 O(n) 的时间复杂度和 O(1) 的空间复杂度解决该问题吗？

来源：力扣（LeetCode）
链接：844. 比较含退格的字符串
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这道题题意其实和当时用栈将计算的值从中缀表达式变成后缀表达式是一个概念。

直接用双栈，遍历字符串，如果碰到 # 这个字符就pop()，如果为字符则push（）进栈。遍历两个栈，比较栈内的字符是否都相同

tips:注意一下string和char的转化。

class Solution {
    public boolean backspaceCompare(String s, String t) {
        Stack ss = backspace(s);
        Stack st = backspace(t);
        while(!ss.empty()&&!st.empty()){
            if(ss.pop() != st.pop()){
                return false;
            }
        } 
        return ss.empty()&&st.empty();
    }

    public Stack backspace(String s){
        Stack temp = new Stack();
        for (Character c : s.toCharArray()) {
            if (c != '#') {
                temp.push(c);
            }
            else if (!temp.empty()) {
                temp.pop();
            }
        }
        return temp;
    }
}

双指针要难理解很多，其实只需要理解指针是怎么走的就可以理解了。

1.首先需要分别指向S和T末尾的两个指针（因为 # 会对它前面的字符起作用，所以从后向前）
2.之后使用两个值分别记录两串未使用的 # 的个数，比如sNumber,tNumber

指针从后向前移动

当指针指向 # 时，number++当指针指向字符，但number大于0时，就将number–而指针指向字符且number为0时，就需要比较此时两个指针所指的字符是否相同，若不同直接false；若相同，继续判断前一个字符，都向前移动一位。

3.当两个指针都顺利走完了两串字符，就可以返回true。

class Solution {
    public boolean backspaceCompare(String s, String t) {
        int sPointer = s.length()-1,tPointer = t.length()-1;
        int sNumber  = 0,tNumber = 0;
        while(sPointer>=0||tPointer>=0){
            while(sPointer>=0){
                if(s.charAt(sPointer) == '#'){
                    sNumber++;
                    sPointer--;
                }
                else if(sNumber>0){
                    sNumber--;
                    sPointer--;
                }
                else{
                    break;
                }
            }
            while(tPointer>=0){
                if(t.charAt(tPointer)=='#'){
                    tNumber++;
                    tPointer--;
                }
                else if(tNumber>0){
                    tNumber--;
                    tPointer--;
                }
                else{
                    break;
                }
            }
            if(tPointer>=0&&sPointer>=0){
                if(t.charAt(tPointer) != s.charAt(sPointer)){
                    return false;
                }
            }
            else {
                if (tPointer>=0||sPointer>=0) {
                    return false;
                }
            }
            sPointer--;
            tPointer--;
        }
         return true;
     }
}