作者: 负雪明烛
id: fuxuemingzhu
个人博客: http://fuxuemingzhu.cn/


题目地址:https://leetcode.com/problems/remove-all-adjacent-duplicates-in-string/

题目描述

Given a string S of lowercase letters, a duplicate removal consists of choosing two adjacent and equal letters, and removing them.

We repeatedly make duplicate removals on S until we no longer can.

Return the final string after all such duplicate removals have been made. It is guaranteed the answer is unique.

Example 1:

Input: "abbaca"
Output: "ca"
Explanation:
For example, in "abbaca" we could remove "bb" since the letters are adjacent and equal, and this is the only possible move. The result of this move is that the string is "aaca", of which only "aa" is possible, so the final string is "ca".

Note:

  1. 1 <= S.length <= 20000
  2. S consists only of English lowercase letters.

题目大意

每次去除字符串中两个相邻且相等的字符,求最后剩下的字符串(结果唯一)。

解题方法

两个相等的字符连续出现则都消除掉,另外题目也说了结果唯一。有点类似与括号匹配问题,所以,我们一个很容易想到栈去解决。

顺序遍历字符串,如果当前的字符和栈顶字符相同,那么出栈;否则,把结果放到栈里面。最后栈里剩余的字符串即为所求。

Python代码如下:

class Solution(object):
def removeDuplicates(self, S):
"""
:type S: str
:rtype: str
"""
stack = []
for s in S:
if stack and s == stack[-1]:
stack.pop()
continue
stack.append(s)
return "".join(stack)

日期

2019 年 5 月 22 日 —— 一个多月不刷题了,重新捡起来

最新文章

  1. php基础_函数和类
  2. codeforces 709A A. Juicer(水题)
  3. RDO部署openstack(1)
  4. opencv-----基本数据类型
  5. Bootstrap学习 - JavaScript插件
  6. java系列笔记---正则表达式(1)常用符号
  7. JVM内存
  8. NHibernate教程(18)--对象状态
  9. 把jmeter获取到的信息存到本地文件
  10. jQuery事件学习
  11. onload事件与ready事件的区别,原生js与jquery的区别
  12. 工作流程引挈 https://www.flowable.org/
  13. 在PHP中使用协程实现多任务调度
  14. (面试)Hash表算法十道海量数据处理面试题
  15. gulp实用配置(1)——demo
  16. Framework连接oracle数据库以及Cognos服务器出现错误
  17. MySQL优化之——权限管理
  18. Spring------SpringBoot中注解
  19. css在线sprite
  20. Java50道经典习题-程序28 排序算法

热门文章

  1. ss 显示socket状态
  2. you crash I crash
  3. PHP生成EXCEL,支持多个SHEET
  4. 生成随机数的N种方式
  5. php代码审计入门前必看
  6. 【模板】单源最短路径(Dijkstra)/洛谷P4779
  7. 容器之分类与各种测试(四)——unordered-multiset
  8. HongYun-ui搭建记录
  9. 【Linux】【Services】【SaaS】Docker+kubernetes(13. 部署Jenkins/Maven实现代码自动化发布)
  10. 深入.NET框架与面向对象的回顾