当前位置 博文首页 > 若能绽放光丶的博客：leetcode题目：844.比较含退格的字符串
我们来分析一下，题目优点让人不太明白，但是说白了，就是‘#’相当于退格，删除‘#’的前面一个，就是字符串真实的样子，在这里我们很容易联想到栈的先进后出的例子。
下面给出一组图解：
class Solution(object):
def backspaceCompare(self, S, T):
"""
:type S: str
:type T: str
:rtype: bool
"""
stack_s = []
stack_t = []
for i in S:
if i == '#':
if len(stack_s) != 0:
stack_s.pop()
else:
continue
else:
stack_s.append(i)
for i in T:
if i == '#':
if len(stack_t) != 0:
stack_t.pop()
else:
continue
else:
stack_t.append(i)
if stack_s == stack_t:
return True
else:
return False
import java.util.Stack;
public class SpaceCompare {
public boolean backspaceCompare(String S, String T) {
Stack stack_s = new Stack();
Stack stack_t = new Stack();
for(int i = 0;i < S.length();i++){
if(S.charAt(i) == '#'){
if(!stack_s.isEmpty()){
stack_s.pop();
}else{
continue;
}
}else{
stack_s.add(S.charAt(i));
}
}
for(int i = 0;i < T.length();i++){
if(T.charAt(i) == '#'){
if(!stack_t.isEmpty()){
stack_t.pop();
}else{
continue;
}
}else{
stack_t.add(T.charAt(i));
}
}
if(stack_s.size() == stack_t.size()){
while(stack_s.size() != 0){
if(stack_s.pop() != stack_t.pop()){
return false;
}
}
}else{
return false;
}
return true;
}
}
我们在做任何一道算法题的时候，都要学会思考多种方法解决问题，从而选择最优解法。
我们知道，‘#’代码退格，删除#之前的元素，那么换言之，我们再访问的时候，只需要跳过#之前的元素就行了。
我们可以从后往前遍历字符串，遇到‘#’的时候，就跳过#之后的那个字符，这样的方法的效率远远高于创建两个栈的方法，而且也节约了大量的空间。
代码就不演示了，很简单，可以自己去试一试。
