[LeetCode] 844. Backspace String Compare_Easy tag: Stack **Two pointers
2024-09-26 19:04:39
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?
建一个helper function, 然后用stack, 如果为'#', 就stack.pop(), 否则append(c), 最后返回"".join(stack). T: O(m+n) S: O(m+n)
**imporve, 可以用two pointers 去实现 T: O(m+n) S: O(1)
Code
class Solution:
def backspaceStringCompare(self, S, T):
def helper(s):
stack = []
for c in s:
if c == '#' and stack:
stack.pop()
elif c != '#':
stack.append(c)
return "".join(stack)
return helper(S) == helper(T)
最新文章
- 用JWT来保护我们的ASP.NET Core Web API
- 浅谈cssText
- ORACLE数据库的导入及导出
- HTML 5 代码
- NOIP 2015 游记
- PAT 1027. 打印沙漏(20)
- Category和Extension
- android平台手电筒开发源代码
- Spring框架学习之第5节
- ng-cookie 的基本使用
- .Net学习难点讨论系列17 - 线程本地变量的使用
- Laravel Migrate
- 宝爷Debug小记——Cocos2d-x(3.13之前的版本)底层BUG导致Spine渲染花屏
- win10 uwp 切换主题
- Android 根据字符串动态获取资源ID
- C语言头文件引用
- iview服务不可以被访问解决办法
- flask基本介绍及虚拟环境
- java_线程
- php调试用的几个小方法
热门文章
- 【分享】IT产业中的三大定理(三) —— 反摩尔定理 (Reverse Moore&#39;s Law)
- mac Intellij Idea Tmocat 启动报 Error running Tomcat: /conf/Catalina
- 第一步 使用sencha touch cmd 4.0 创建项目、打包(加入全局变量、公用类、自定义扩展、资源文件)
- Google浏览器清除缓存快捷键
- 记录一下gitlab通过CAS登录慢的问题
- Centos 升级 python
- javaAgent 参数
- 【CF896D】Nephren Runs a Cinema 卡特兰数+组合数+CRT
- Unity3D笔记 愤怒的小鸟<;七>; 小鸟群准备动画
- Function学习