X

LEETCODE 844. Backspace String Compare 解题思路分析

题目大意:

比较含退格的字符串

给定 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. ST 只含有小写字母以及字符 '#'

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: 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-解题思路分析/
Categories: leetcode
kwantong: