题目
- 概述:给定两个含退格的字符串,比较这两个字符串的有效部分是否相等
退格表示自己本身和靠近它左侧的第一个字符(如果有的话)是无效字符
- 输入:
- 字符串S,范围[1, 200]
- 字符串T,范围[1, 200]
S和T只含有小写字符和退格字符'#'
-
输出:两个字符串的有效部分是否相等
-
出处:https://leetcode-cn.com/problems/backspace-string-compare/
思路
-
由于题目中包含退格这一关键字,可以考虑用栈来做
-
对于将要入栈的字符串S中的字符c,如果c为'#',则弹出栈顶元素(如果栈不为空的话),否则将c入栈,对字符串T做相同处理
-
依次弹出两个栈中的元素,若所有元素都相等,则两个字符串相等,反之则不相等
代码
class Solution {
public boolean backspaceCompare(String S, String T) {
LinkedList<Character> sStack = new LinkedList<>();
LinkedList<Character> tStack = new LinkedList<>();
for (char c : S.toCharArray()) {
if (c == '#') {
if (!sStack.isEmpty()) {
sStack.pop();
}
} else {
sStack.push(c);
}
}
for (char c : T.toCharArray()) {
if (c == '#') {
if (!tStack.isEmpty()) {
tStack.pop();
}
} else {
tStack.push(c);
}
}
while (!sStack.isEmpty() && !tStack.isEmpty()) {
if (sStack.pop() != tStack.pop()) {
return false;
}
}
return sStack.isEmpty() && tStack.isEmpty();
}
}
网友评论