匹配问题都是栈的强项
1047. 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S,重复项删除操作会选择两个相邻且相同的字母,并删除它们。
在 S 上反复执行重复项删除操作,直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
示例:
- 输入:"abbaca"
- 输出:"ca"
- 解释:例如,在 "abbaca" 中,我们可以删除 "bb" 由于两字母相邻且相同,这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca",其中又只有 "aa" 可以执行重复项删除操作,所以最后的字符串为 "ca"。
提示:
- 1 <= S.length <= 20000
- S 仅由小写英文字母组成。
思路
正题
本题要删除相邻相同元素,相对于20. 有效的括号来说其实也是匹配问题,20. 有效的括号 是匹配左右括号,本题是匹配相邻元素,最后都是做消除的操作。
本题也是用栈来解决的经典题目。
那么栈里应该放的是什么元素呢?
我们在删除相邻重复项的时候,其实就是要知道当前遍历的这个元素,我们在前一位是不是遍历过一样数值的元素,那么如何记录前面遍历过的元素呢?
所以就是用栈来存放,那么栈的目的,就是存放遍历过的元素,当遍历当前的这个元素的时候,去栈里看一下我们是不是遍历过相同数值的相邻元素。
然后再去做对应的消除操作。 如动画所示:
从栈中弹出剩余元素,此时是字符串ac,因为从栈里弹出的元素是倒序的,所以再对字符串进行反转一下,就得到了最终的结果。
C++代码 :
class Solution {
public:
string removeDuplicates(string S) {
stack<char> st;
for (char s : S) {
if (st.empty() || s != st.top()) {
st.push(s);
} else {
st.pop(); // s 与 st.top()相等的情况
}
}
string result = "";
while (!st.empty()) { // 将栈中元素放到result字符串汇总
result += st.top();
st.pop();
}
reverse (result.begin(), result.end()); // 此时字符串需要反转一下
return result;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(n)
当然可以拿字符串直接作为栈,这样省去了栈还要转为字符串的操作。
代码如下:
class Solution {
public:
string removeDuplicates(string S) {
string result;
for(char s : S) {
if(result.empty() || result.back() != s) {
result.push_back(s);
}
else {
result.pop_back();
}
}
return result;
}
};
- 时间复杂度: O(n)
- 空间复杂度: O(1),返回值不计空间复杂度
题外话
这道题目就像是我们玩过的游戏对对碰,如果相同的元素挨在一起就要消除。
可能我们在玩游戏的时候感觉理所当然应该消除,但程序又怎么知道该如何消除呢,特别是消除之后又有新的元素可能挨在一起。
此时游戏的后端逻辑就可以用一个栈来实现(我没有实际考察对对碰或者爱消除游戏的代码实现,仅从原理上进行推断)。
游戏开发可能使用栈结构,编程语言的一些功能实现也会使用栈结构,实现函数递归调用就需要栈,但不是每种编程语言都支持递归,例如:
递归的实现就是:每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈中,然后递归返回的时候,从栈顶弹出上一次递归的各项参数,所以这就是递归为什么可以返回上一层位置的原因。
相信大家应该遇到过一种错误就是栈溢出,系统输出的异常是Segmentation fault
(当然不是所有的Segmentation fault
都是栈溢出导致的) ,如果你使用了递归,就要想一想是不是无限递归了,那么系统调用栈就会溢出。
而且在企业项目开发中,尽量不要使用递归!在项目比较大的时候,由于参数多,全局变量等等,使用递归很容易判断不充分return的条件,非常容易无限递归(或者递归层级过深),造成栈溢出错误(这种问题还不好排查!)
其他语言版本
Java:
使用 Deque 作为堆栈
class Solution {
public String removeDuplicates(String S) {
//ArrayDeque会比LinkedList在除了删除元素这一点外会快一点
//参考:https://stackoverflow.com/questions/6163166/why-is-arraydeque-better-than-linkedlist
ArrayDeque<Character> deque = new ArrayDeque<>();
char ch;
for (int i = 0; i < S.length(); i++) {
ch = S.charAt(i);
if (deque.isEmpty() || deque.peek() != ch) {
deque.push(ch);
} else {
deque.pop();
}
}
String str = "";
//剩余的元素即为不重复的元素
while (!deque.isEmpty()) {
str = deque.pop() + str;
}
return str;
}
}
拿字符串直接作为栈,省去了栈还要转为字符串的操作。
class Solution {
public String removeDuplicates(String s) {
// 将 res 当做栈
// 也可以用 StringBuilder 来修改字符串,速度更快
// StringBuilder res = new StringBuilder();
StringBuffer res = new StringBuffer();
// top为 res 的长度
int top = -1;
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
// 当 top > 0,即栈中有字符时,当前字符如果和栈中字符相等,弹出栈顶字符,同时 top--
if (top >= 0 && res.charAt(top) == c) {
res.deleteCharAt(top);
top--;
// 否则,将该字符 入栈,同时top++
} else {
res.append(c);
top++;
}
}
return res.toString();
}
}
拓展:双指针
class Solution {
public String removeDuplicates(String s) {
char[] ch = s.toCharArray();
int fast = 0;
int slow = 0;
while(fast < s.length()){
// 直接用fast指针覆盖slow指针的值
ch[slow] = ch[fast];
// 遇到前后相同值的,就跳过,即slow指针后退一步,下次循环就可以直接被覆盖掉了
if(slow > 0 && ch[slow] == ch[slow - 1]){
slow--;
}else{
slow++;
}
fast++;
}
return new String(ch,0,slow);
}
}
Python:
# 方法一,使用栈
class Solution:
def removeDuplicates(self, s: str) -> str:
res = list()
for item in s:
if res and res[-1] == item:
res.pop()
else:
res.append(item)
return "".join(res) # 字符串拼接
# 方法二,使用双指针模拟栈,如果不让用栈可以作为备选方法。
class Solution:
def removeDuplicates(self, s: str) -> str:
res = list(s)
slow = fast = 0
length = len(res)
while fast < length:
# 如果一样直接换,不一样会把后面的填在slow的位置
res[slow] = res[fast]
# 如果发现和前一个一样,就退一格指针
if slow > 0 and res[slow] == res[slow - 1]:
slow -= 1
else:
slow += 1
fast += 1
return ''.join(res[0: slow])
Go:
func removeDuplicates(s string) string {
var stack []byte
for i := 0; i < len(s);i++ {
// 栈不空 且 与栈顶元素不等
if len(stack) > 0 && stack[len(stack)-1] == s[i] {
// 弹出栈顶元素 并 忽略当前元素(s[i])
stack = stack[:len(stack)-1]
}else{
// 入栈
stack = append(stack, s[i])
}
}
return string(stack)
}
JavaScript:
法一:使用栈
var removeDuplicates = function(s) {
const result = []
for(const i of s){
if(i === result[result.length-1]){
result.pop()
}else{
result.push(i)
}
}
return result.join('')
};
法二:双指针(模拟栈)
// 原地解法(双指针模拟栈)
var removeDuplicates = function(s) {
s = [...s];
let top = -1; // 指向栈顶元素的下标
for(let i = 0; i < s.length; i++) {
if(top === -1 || s[top] !== s[i]) { // top === -1 即空栈
s[++top] = s[i]; // 入栈
} else {
top--; // 推出栈
}
}
s.length = top + 1; // 栈顶元素下标 + 1 为栈的长度
return s.join('');
};
TypeScript:
function removeDuplicates(s: string): string {
const helperStack: string[] = [];
let i: number = 0;
while (i < s.length) {
let top: string = helperStack[helperStack.length - 1];
if (top === s[i]) {
helperStack.pop();
} else {
helperStack.push(s[i]);
}
i++;
}
let res: string = '';
while (helperStack.length > 0) {
res = helperStack.pop() + res;
}
return res;
};
C:
方法一:使用栈
char * removeDuplicates(char * s){
//求出字符串长度
int strLength = strlen(s);
//开辟栈空间。栈空间长度应为字符串长度+1(为了存放字符串结束标志'\0')
char* stack = (char*)malloc(sizeof(char) * strLength + 1);
int stackTop = 0;
int index = 0;
//遍历整个字符串
while(index < strLength) {
//取出当前index对应字母,之后index+1
char letter = s[index++];
//若栈中有元素,且栈顶字母等于当前字母(两字母相邻)。将栈顶元素弹出
if(stackTop > 0 && letter == stack[stackTop - 1])
stackTop--;
//否则将字母入栈
else
stack[stackTop++] = letter;
}
//存放字符串结束标志'\0'
stack[stackTop] = '\0';
//返回栈本身作为字符串
return stack;
}
方法二:双指针法
char * removeDuplicates(char * s){
//创建快慢指针
int fast = 0;
int slow = 0;
//求出字符串长度
int strLength = strlen(s);
//遍历字符串
while(fast < strLength) {
//将当前slow指向字符改为fast指向字符。fast指针+1
char letter = s[slow] = s[fast++];
//若慢指针大于0,且慢指针指向元素等于字符串中前一位元素,删除慢指针指向当前元素
if(slow > 0 && letter == s[slow - 1])
slow--;
else
slow++;
}
//在字符串结束加入字符串结束标志'\0'
s[slow] = 0;
return s;
}
Swift:
func removeDuplicates(_ s: String) -> String {
var stack = [Character]()
for c in s {
if stack.last == c {
stack.removeLast()
} else {
stack.append(c)
}
}
return String(stack)
}
C#:
public string RemoveDuplicates(string s) {
//拿字符串直接作为栈,省去了栈还要转为字符串的操作
StringBuilder res = new StringBuilder();
foreach(char c in s){
if(res.Length > 0 && res[res.Length-1] == c){
res.Remove(res.Length-1, 1);
}else{
res.Append(c);
}
}
return res.ToString();
}
PHP:
class Solution {
function removeDuplicates($s) {
$stack = new SplStack();
for($i=0;$i<strlen($s);$i++){
if($stack->isEmpty() || $s[$i] != $stack->top()){
$stack->push($s[$i]);
}else{
$stack->pop();
}
}
$result = "";
while(!$stack->isEmpty()){
$result.= $stack->top();
$stack->pop();
}
// 此时字符串需要反转一下
return strrev($result);
}
}
Scala:
object Solution {
import scala.collection.mutable
def removeDuplicates(s: String): String = {
var stack = mutable.Stack[Int]()
var str = "" // 保存最终结果
for (i <- s.indices) {
var tmp = s(i)
// 如果栈非空并且栈顶元素等于当前字符,那么删掉栈顶和字符串最后一个元素
if (!stack.isEmpty && tmp == stack.head) {
str = str.take(str.length - 1)
stack.pop()
} else {
stack.push(tmp)
str += tmp
}
}
str
}
}
Rust:
impl Solution {
pub fn remove_duplicates(s: String) -> String {
let mut stack = vec![];
let mut chars: Vec<char> = s.chars().collect();
while let Some(c) = chars.pop() {
if stack.is_empty() || stack[stack.len() - 1] != c {
stack.push(c);
} else {
stack.pop();
}
}
stack.into_iter().rev().collect()
}
}
Ruby
def remove_duplicates(s)
#数组模拟栈
stack = []
s.each_char do |chr|
if stack.empty?
stack.push chr
else
head = stack.pop
#重新进栈
stack.push head, chr if head != chr
end
end
return stack.join
end