844. 比较含退格的字符串

不念不忘少年蓝@ 2022-12-16 15:22 84阅读 0赞

给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 \# 代表退格字符。

注意：如果对空文本输入退格字符，文本继续为空。

**示例 1：**

输入：S = "ab#c", T = "ad#c"
    输出：true
    解释：S 和 T 都会变成 “ac”。

**示例 2：**

输入：S = "ab##", T = "c#d#"
    输出：true
    解释：S 和 T 都会变成 “”。

解法1:  从前向后处理

class Solution:
        def backspaceCompare(self, S: str, T: str) -> bool:
            flag = False
    
            S_len = len(S)
            T_len = len(T)
            min_len = min(S_len, T_len)
            # 一次遍历解决
            s_list = ''
            t_list = ''
            for i in range(min_len):
                if S[i] == '#':
                    s_list = s_list[:-1]
                else:
                    s_list += S[i]
                if T[i] == '#':
                    t_list = t_list[:-1]
                else:
                    t_list += T[i]
            # 处理完成
            if S_len > min_len:
                i = min_len
                while i < S_len:
                    if S[i] == '#':
                        s_list = s_list[:-1]
                    else:
                        s_list += S[i]
                    i = i + 1
            if T_len > min_len:
                i = min_len
                while i < T_len:
                    if T[i] == '#':
                        t_list = t_list[:-1]
                    else:
                        t_list += T[i]
                    i = i +1
            if t_list == s_list:
                return True
            return False

解法2: 从后向前

class Solution:
        def backspaceCompare(self, S: str, T: str) -> bool:
            # 从后向前遍历 
            s_len = len(S)
            t_len = len(T)
            i = s_len - 1
            j = t_len - 1
            while i >= 0 or j >= 0:  # 此处为or 两个都应遍历完毕。
                # 分别对 S, T 从后向前 遍历，找到 有效字符 进行比较;
                s_b = 0
                while i >= 0:
                    if S[i] == '#':
                        s_b += 1
                    else:  # 针对 ### 多个#连着的情况， 
                        if s_b != 0:  # 可以用来 跳过 无效字符，妙极
                            s_b = s_b - 1
                        else:
                            break
                    i = i - 1
                t_b = 0
                while j >= 0:
                    if T[j] == '#':
                        t_b += 1
                    else:
                        if t_b != 0:
                            t_b = t_b - 1
                        else:
                            break  # 从这跳出， 就可以比较 
                    j = j - 1
                if j >=0 and i >=0:
                    if S[i] != T[j]:
                        return False
                    j = j - 1
                    i = i - 1
                else:
                    break
            return i < 0 and j < 0 # 都小于0 则为true， 否则false

每次给自己立flag都坚持不住， 每天刷一题 都坚持不住。 到底什么事情是最重要的， 一个人不能每天都只做一件事的。