LeetCode刷题（143）～比较含退格的字符串

题目描述

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

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

示例 1：

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

  

 

  
1
  
2
  
3
 

示例 2：

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

  

 

  
1
  
2
  
3
 

示例 3：

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

  

 

  
1
  
2
  
3
 

示例 4：

输入：S = "a#c", T = "b"
输出：false
解释：S 会变成 “c”，但 T 仍然是 “b”。
 

  

 

  
1
  
2
  
3
  
4
 

提示：

• 1 <= S.length <= 200
• 1 <= T.length <= 200
• S 和 T 只含有小写字母以及字符 ‘#’。

进阶：

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

解答 By 海轰

提交代码

bool backspaceCompare(string S, string T) { stack<char> s1; stack<char> s2; for(char i:S) { if(i=='#'&&!s1.empty()) s1.pop(); else if(i!='#') s1.push(i); } for(char i:T) { if(i=='#'&&!s2.empty()) s2.pop(); else if(i!='#') s2.push(i); } if(s1.size()!=s2.size()) return false; while(!s1.empty()) { if(s1.top()!=s2.top()) return false; else { s1.pop(); s2.pop(); } } return 1; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
 

运行结果

提交代码（优化）

stack<char> a(string s) { stack<char> ans; for(char i:s) { if(i!='#') ans.push(i); else if(!ans.empty()) ans.pop(); } return ans; } bool backspaceCompare(string S, string T) { stack<char> s1,s2; s1=a(S); s2=a(T); return s1==s2; }

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
 

运行结果

题目来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/backspace-string-compare

文章来源: haihong.blog.csdn.net，作者：海轰Pro，版权归原作者所有，如需转载，请联系作者。

原文链接：haihong.blog.csdn.net/article/details/108521042