[LeetCode] 844. Backspace String Compare 退格字符串比较
2024-10-20 01:23:21
Given two strings S
and T
, return if they are equal when both are typed into empty text editors. #
means a backspace character.
Example 1:
Input: S = "ab#c", T = "ad#c"
Output: true
Explanation: Both S and T become "ac".
Example 2:
Input: S = "ab##", T = "c#d#"
Output: true
Explanation: Both S and T become "".
Example 3:
Input: S = "a##c", T = "#a#c"
Output: true
Explanation: Both S and T become "c".
Example 4:
Input: S = "a#c", T = "b"
Output: false
Explanation: S becomes "c" while T becomes "b".
Note:
1 <= S.length <= 200
1 <= T.length <= 200
S
andT
only contain lowercase letters and'#'
characters.
Follow up:
- Can you solve it in
O(N)
time andO(1)
space?
给2个字符串S和T,里面含有#代表退格键,意味着前面的字符会被删除,判断2个字符串是否相等,字符串中只含有小写字母和#。
解法1:用一个栈存字符,循环字符串,如果是字母就加入栈,遇到#而且栈里面有字母就pop出栈里最后的字符。T: O(n), S:(n)
解法2:follow up要求O(N) time and O(1) space,在一个循环里,从后往前处理字符串,用一个变量记录要删除的字符数量,遇到#时变量加1,遇到字符并且变量大于1,变量减1,直到没遇到#并且要变量为0,这时比较两个字符此时是否一样,不一样返回false,如果字符串比较完没有不一样的字符出现,返回ture。
G家:follow up: 如果有大写键CAP
Java: O(1) space
public boolean backspaceCompare(String S, String T) {
int i = S.length() - 1, j = T.length() - 1;
while (true) {
for (int back = 0; i >= 0 && (back > 0 || S.charAt(i) == '#'); --i)
back += S.charAt(i) == '#' ? 1 : -1;
for (int back = 0; j >= 0 && (back > 0 || T.charAt(j) == '#'); --j)
back += T.charAt(j) == '#' ? 1 : -1;
if (i >= 0 && j >= 0 && S.charAt(i) == T.charAt(j)) {
i--; j--;
} else
return i == -1 && j == -1;
}
}
Python:
def backspaceCompare(self, S, T):
i, j = len(S) - 1, len(T) - 1
backS = backT = 0
while True:
while i >= 0 and (backS or S[i] == '#'):
backS += 1 if S[i] == '#' else -1
i -= 1
while j >= 0 and (backT or T[j] == '#'):
backT += 1 if T[j] == '#' else -1
j -= 1
if not (i >= 0 and j >= 0 and S[i] == T[j]):
return i == j == -1
i, j = i - 1, j - 1
Python:
# Time: O(m + n)
# Space: O(1)
import itertools class Solution(object):
def backspaceCompare(self, S, T):
"""
:type S: str
:type T: str
:rtype: bool
"""
def findNextChar(S):
skip = 0
for i in reversed(xrange(len(S))):
if S[i] == '#':
skip += 1
elif skip:
skip -= 1
else:
yield S[i] return all(x == y for x, y in
itertools.izip_longest(findNextChar(S), findNextChar(T)))
Python: wo O(n) space
class Solution(object):
def backspaceCompare(self, S, T):
"""
:type S: str
:type T: str
:rtype: bool
"""
s1, s2 = [], []
for i in range(len(S)):
if S[i] == '#' and s1:
s1.pop()
elif S[i] == '#':
continue
else:
s1.append(S[i]) for j in range(len(T)):
if T[j] == '#' and s2:
s2.pop()
elif T[j] == '#':
continue
else:
s2.append(T[j]) return s1 == s2
C++:
bool backspaceCompare(string S, string T) {
int i = S.length() - 1, j = T.length() - 1;
while (1) {
for (int back = 0; i >= 0 && (back || S[i] == '#'); --i)
back += S[i] == '#' ? 1 : -1;
for (int back = 0; j >= 0 && (back || T[j] == '#'); --j)
back += T[j] == '#' ? 1 : -1;
if (i >= 0 && j >= 0 && S[i] == T[j])
i--, j--;
else
return i == -1 && j == -1;
}
}
All LeetCode Questions List 题目汇总
最新文章
- 基于Ajax+div的“左边菜单、右边内容”页面效果实现
- 【算法杂谈】LJX的迪杰斯特拉算法报告
- WEB打印控件Lodop
- When to use dequeueReusableCellWithIdentifier vs dequeueReusableCellWithIdentifier: forIndexPath
- C#winform控制textbox输入只能为数字
- Protractor AngularJS测试框架教程
- mysql 5.7 zip 文件在 windows下的安装
- application&#160;windows&#160;are&#160;expected&#160;to&#160;have&#160;a&#160;root&#160;view&#160;controller错误
- 微信小程序之----加载中提示框loading
- 用java来实现验证码功能。
- None.js 第三步 回调函数【阻塞代码--非阻塞代码】
- django项目的部署
- VS2008中开发智能设备程序的一些总结收藏
- PHP 类文件的自动加载机制 __autoload()
- at91sam9260 笔记1
- [BZOJ4565][HAOI2016]字符合并(区间状压DP)
- MQ环境的搭建
- Oracle中sign/decode/nvl/round/trunc/(+)/instr/substr/replace解释
- 洛谷3004 [USACO10DEC]宝箱Treasure Chest
- POJ:2674-Linear world(名字交换碰撞)