関小君刷题记

题目大意：

比较含退格的字符串

给定 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. 1 <= S.length <= 200
2. 1 <= T.length <= 200
3. S 和 T 只含有小写字母以及字符 '#'。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=844

解题思路分析：

1. 使用2个Stack栈分别存储S和T中字符。当遇到退格键（#）以外的字符时，将该字符入栈。反之当遇到退格键（#）时，如果栈中元素个数不为0，将栈顶元素pop出栈（相当于退格处理）。直到循环完所有字符，最后栈中保留下的元素，即是编辑后的文本。
2. 如果2个Stack栈的元素个数不同，直接返回false。
3. 如果2个栈中元素个数相同，循环每一位，如果当前位上两个栈中的元素不同，返回false。如果都相同，返回true。

实现代码：

public boolean backspaceCompare(String S, String T) {
    Stack<Character> ss = new Stack<>(); // 字符串S用的栈
    for(char c : S.toCharArray()){ // 循环S中每个字符
        if(c=='#'){ // 如果当前字符是#
            if(ss.size()>0) ss.pop(); // 如果栈中元素个数大于0，pop出栈一个元素
        }else ss.push(c); // 如果当前字符不是#，将当前字符push入栈
    }
    Stack<Character> st = new Stack<>(); // 字符串T用的栈
    for(char c : T.toCharArray()){
        if(c=='#'){
            if(st.size()>0) st.pop();
        }else st.push(c);
    }
    // 如果两个栈中元素个数不同，返回false
    if(ss.size()!=st.size()) return false;
    // 比较两个Stack中每一位上的字符是否相同
    while(ss.size()>0){
        if(ss.pop()!=st.pop()) return false;
    }
    return true;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 66.83% of Java online submissions for Backspace String Compare.

Memory Usage: 37.8 MB, less than 6.06% of Java online submissions for Backspace String Compare.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-844-backspace-string-compare-解题思路分析/