一【题目类别】

• 栈

二【题目难度】

• 简单

三【题目编号】

• 844.比较含退格的字符串

四【题目描述】

• 给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符。
• 注意：如果对空文本输入退格字符，文本继续为空。

五【题目示例】

• 示例 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 = “b”
  • 输出：false
  • 解释：s 会变成 “c”，但 t 仍然是 “b”。

六【题目提示】

• 1 <= s.length, t.length <= 200
• s 和 t 只含有小写字母以及字符 ‘#’

七【题目进阶】

• 进阶：你可以用 $O(n)$ 的时间复杂度和 $O(1)$ 的空间复杂度解决该问题吗？

八【解题思路】

• 利用栈的思想
• 遇到不是‘#’就入栈
• 遇到‘#’如果栈不空就退栈，如果栈空不进行操作
• 最后先比较栈长度，如果长度不相同肯定不是相同的字符串
• 然后一一比较栈元素，如果有不相同的肯定也不是相同的字符串
• 如果都没问题就是相同的字符串

九【时间频度】

• 时间复杂度：$O(n)$，其中 $n$ 是数组元素个数
• 空间复杂度：C语言为$O(1)$，Java语言为$O(n)$，其中 $n$ 是数组元素个数

十【代码实现】

1. Java语言版

package Stack;

import java.util.Stack;

public class p844_CompareStringsWithBackspaces {
    

    public static void main(String[] args) {
    
        String s = "ab#c";
        String t = "ad#c";
        boolean res = backspaceCompare(s, t);
        System.out.println("res = " + res);
    }

    public static boolean backspaceCompare(String s, String t) {
    
        Stack stackS = new Stack();
        Stack stackT = new Stack();
        for (int i = 0; i < s.length(); i++) {
    
            if (s.charAt(i) != '#') {
    
                stackS.push(s.charAt(i));
            } else {
    
                if (!stackS.isEmpty()) {
    
                    stackS.pop();
                } else {
    
                    continue;
                }
            }
        }
        for (int i = 0; i < t.length(); i++) {
    
            if (t.charAt(i) != '#') {
    
                stackT.push(t.charAt(i));
            } else {
    
                if (!stackT.isEmpty()) {
    
                    stackT.pop();
                } else {
    
                    continue;
                }
            }
        }
        if (stackS.size() != stackT.size()) {
    
            return false;
        } else {
    
            while (!stackS.isEmpty()) {
    
                if (stackS.pop() != stackT.pop()) {
    
                    return false;
                }
            }
        }
        return true;
    }

}

2. C语言版

#include<stdio.h>
#include<stdbool.h>

bool backspaceCompare(char * s, char * t)
{
    
	int topS = -1;
	int topT = -1;
	for (int i = 0; i < strlen(s); i++)
	{
    
		if (s[i] != '#')
		{
    
			s[++topS] = s[i];
		}
		else
		{
    
			if (topS != -1)
			{
    
				topS--;
			}
			else
			{
    
				topS = -1;
			}
		}
	}
	for (int i = 0; i < strlen(t); i++)
	{
    
		if (t[i] != '#')
		{
    
			t[++topT] = t[i];
		}
		else
		{
    
			if (topT != -1)
			{
    
				topT--;
			}
			else
			{
    
				topT = -1;
			}
		}
	}
	if (topS != topT)
	{
    
		return false;
	}
	else
	{
    
		for (int i = 0; i <= topS; i++)
		{
    
			if (s[i] != t[i])
			{
    
				return false;
			}
		}
	}
	return true;
}

/*主函数省略*/

十一【提交结果】

1. Java语言版
   

2. C语言版