序
本文次要记录一下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
- 比拟含退格的字符串