Keshawn_lu's Blog

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

字数统计: 390阅读时长: 1 min
2020/10/19 Share

题目简介:

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

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

示例 1:

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

示例 2:

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

示例 3:

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

示例 4:

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

提示:

  1. 1 <= S.length <= 200
  2. 1 <= T.length <= 200
  3. ST 只含有小写字母以及字符 '#'

    思路:

利用栈:

  • 若遇到#,则将栈顶元素弹出(在栈中有元素的情况下)
  • 若遇到普通字符,则将其压入栈。

最后比较两个栈内的元素是否相等即可。

代码如下:

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
public:
bool backspaceCompare(string S, string T) {

stack<char> stk;
stack<char> stk2;

for(int i = 0; i < S.size(); i++){

if(S[i] == '#' && stk.empty())
continue;

if(S[i] == '#')
stk.pop();
else
stk.push(S[i]);
}

for(int j = 0; j < T.size(); j++){

if(T[j] == '#' && stk2.empty())
continue;

if(T[j] == '#')
stk2.pop();
else
stk2.push(T[j]);
}

while(!stk.empty() && !stk2.empty()){

if(stk.top() != stk2.top())
return false;

stk.pop();
stk2.pop();
}

if(stk.empty() && stk2.empty())
return true;
else
return false;
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: