Skip to content

Latest commit

 

History

History
89 lines (82 loc) · 2.92 KB

File metadata and controls

89 lines (82 loc) · 2.92 KB

844. 比较含退格的字符串

https://leetcode-cn.com/problems/backspace-string-compare/

Java

/*
 * @Author: Goog Tech
 * @Date: 2020-08-30 17:19:51
 * @LastEditTime: 2020-08-30 17:20:08
 * @Description: https://leetcode-cn.com/problems/backspace-string-compare/
 * @FilePath: \leetcode-googtech\#844. Backspace String Compare\Solution.java
 * @WebSite: https://algorithm.show/
 */

class Solution {

    // 本题主要考察双指针,这里利用栈结构来解答下吧嘿嘿😅
    public boolean backspaceCompare(String S, String T) {
        // 初始化栈结构,其用于存储 S 与 T 字符串中的字符
        Stack<Character> sstack = new Stack<>();
        Stack<Character> tstack = new Stack<>();
        // 遍历字符串 S 中的字符
        for(int i = 0; i < S.length(); i++) {
            // 判断当前字符是否等于符号 #
            if(S.charAt(i) != '#') {
                // 若不等于则将其压入栈中
                sstack.push(S.charAt(i));
            // 判断当前栈是否为空
            }else if(!sstack.isEmpty()) {
                // 若不为空则弹出栈顶元素,即删除符号 # 前的一个字符
                sstack.pop();
            }
        }
        // 同上
        for(int j = 0; j < T.length(); j++) {
            if(T.charAt(j) != '#') {
                tstack.push(T.charAt(j));
            }else if(!tstack.isEmpty()) {
                tstack.pop();
            }
        }
        // 最后判断两个栈中的元素是否相同,并返回其结果
        return sstack.equals(tstack);
    }
}

Python

'''
Author: Goog Tech
Date: 2020-08-30 17:19:55
LastEditTime: 2020-08-30 17:21:07
Description: https://leetcode-cn.com/problems/backspace-string-compare/
FilePath: \leetcode-googtech\#844. Backspace String Compare\Solution.py
WebSite: https://algorithm.show/
'''

class Solution(object):

    # 本题主要考察双指针,这里利用栈结构来解答下吧嘿嘿😅
    def backspaceCompare(self, S, T):
        """
        :type S: str
        :type T: str
        :rtype: bool
        """
        # 初始化两辅助栈,其用于存储 S 与 T 字符串中的字符
        slist, tlist = [], []
        # 遍历 S 字符串中的字符
        for i in range(len(S)):
            # 判断当前字符是否为符号 #
            if S[i] != '#':
                # 若是则将其压入栈中
                slist.append(S[i])
            # 判断当前字符是否为符号 # 且辅助栈是否为空
            elif S[i] == '#' and slist != []:
                # 若是则弹出栈顶元素,即删除符号 # 前的一个字符
                slist.pop()
        # 同上
        for j in range(len(T)):
            if T[j] != '#':
                tlist.append(T[j])
            elif T[j] == '#' and tlist != []:
                tlist.pop()
        # 判断两个辅助栈中的元素是否相同,并返回其结果
        return slist == tlist