美文网首页
栈-E844-比较含退格的字符串

栈-E844-比较含退格的字符串

作者: 三次元蚂蚁 | 来源:发表于2019-03-24 11:30 被阅读0次

题目

  • 概述:给定两个含退格的字符串,比较这两个字符串的有效部分是否相等

退格表示自己本身和靠近它左侧的第一个字符(如果有的话)是无效字符

  • 输入:
  1. 字符串S,范围[1, 200]
  2. 字符串T,范围[1, 200]

S和T只含有小写字符和退格字符'#'

思路

  • 由于题目中包含退格这一关键字,可以考虑用栈来做

  • 对于将要入栈的字符串S中的字符c,如果c为'#',则弹出栈顶元素(如果栈不为空的话),否则将c入栈,对字符串T做相同处理

  • 依次弹出两个栈中的元素,若所有元素都相等,则两个字符串相等,反之则不相等

代码

class Solution {
    public boolean backspaceCompare(String S, String T) {
        LinkedList<Character> sStack = new LinkedList<>();
        LinkedList<Character> tStack = new LinkedList<>();
        for (char c : S.toCharArray()) {
            if (c == '#') {
                if (!sStack.isEmpty()) {
                    sStack.pop();
                }
            } else {
                sStack.push(c);
            }
        }
        for (char c : T.toCharArray()) {
            if (c == '#') {
                if (!tStack.isEmpty()) {
                    tStack.pop();
                }
            } else {
                tStack.push(c);
            }
        }
        
        while (!sStack.isEmpty() && !tStack.isEmpty()) {
            if (sStack.pop() != tStack.pop()) {
                return false;
            }
        }
        return sStack.isEmpty() && tStack.isEmpty();
    }
}

相关文章

网友评论

      本文标题:栈-E844-比较含退格的字符串

      本文链接:https://www.haomeiwen.com/subject/dtzyvqtx.html