关于leetcode:leetcode栈之比较含退格的字符串

序

本文次要记录一下 leetcode 栈之比拟含退格的字符串

题目

给定 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 <= 200
    1 <= T.length <= 200
    S 和 T 只含有小写字母以及字符 '#'。进阶：你能够用 O(N) 的工夫复杂度和 O(1) 的空间复杂度解决该问题吗？起源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/backspace-string-compare
著作权归领扣网络所有。商业转载请分割官网受权，非商业转载请注明出处。

题解

class Solution {public boolean backspaceCompare(String S, String T) {Stack<Character> stackS = processBackspace(S);
        Stack<Character> stackT = processBackspace(T);
        if(stackS.size()!=stackT.size()){return false;}
        while (!stackS.isEmpty()){if(stackS.pop()!=stackT.pop()){return false;}
        }
        return true;
    }

    public Stack<Character> processBackspace(String str) {Stack<Character> result = new Stack<>();
        for(char data: str.toCharArray()){if(data == '#'){if(!result.isEmpty()){result.pop();
                }
            } else {result.push(data);
            }
        }
        return result;
    }
}

小结

这里借助栈，遍历 string 的 char，遇到 # 时在栈不为空的时候 pop 一下，非 # 时则 push 数据到栈中；之后比照两个栈的元素来判断是否相等。

doc

• 比拟含退格的字符串