leetcode1047：删除字符串中的所有相邻重复项

[sisterAn]

给出由小写字母组成的字符串 S ，重复项删除操作 会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

1. <= S.length <= 20000
2. S 仅由小写英文字母组成。

附leetcode地址：leetcode

[Makus577]

使用栈，进栈之前跟栈顶比较，如果不同则进栈，如果相同则栈顶元素出栈

var removeDuplicates = function(S){
 let stack = [S[0]]
 for (let i = 1; i < S.length; i++){
 if (S[i] === stack[stack.length - 1]){
 stack.pop()
 } else{
 stack.push(S[i])
 }
 }
 return stack.join('')
};

时间复杂度 O(n)
空间复杂度 O(n)

[7777sea]

var removeDuplicates = function(S){
 let _ = [];
 for(let i of S){
 if(_.length && _[_.length - 1] == i){
 _.splice(_.length - 1, 1)
 }else{
 _.push(i)
 }
 }
 return _.join('')	
};

[fanefanes]

解题思路：
新建Stack ；
遍历字符串S => S[i]；
if Stack.top() === S[i] => Stack.pop
else => Stack.push(S[i])

 function Duplicates(S){
 let Stack = []
 let L = 0
 let SL = S.length
 for(let i = 0; i< SL;i++){ 
 if(S[i] === Stack[L-1] ){
 Stack.pop()
 --L
 }else{
 Stack.push(S[i])
 ++L
 }
 }
 return Stack.join('')
 }
 }

时间复杂度 O(n),空间复杂度 O(n)

[thxiami]

@fanefanes
提个小建议: 变量L可以去掉的, 因为L === Stack.length

[fanefanes]

@fanefanes
提个小建议: 变量L可以去掉的, 因为L === Stack.length

遍历的时候尽量赋值常量， 要不然for每次循环会进行一次数组遍历查询 获取length

[thxiami]

@fanefanes
提个小建议: 变量L可以去掉的, 因为L === Stack.length

遍历的时候尽量赋值常量， 要不然for每次循环会进行一次数组遍历查询 获取length

获取数组的 length 应该不需要遍历数组才能获得吧, 这是它的一个属性, O(1)的时间复杂度

[wufeicris]

var removeDuplicates = function(S){
 let stack = []
 for(let v of S){
 let peek = stack[stack.length-1]
 if( peek === v){
 stack.pop()
 }else{
 stack.push(v)
 }
 }
 return stack.join('')
};

[sisterAn]

解法：利用栈

解题思路： 遍历字符串，依次入栈，入栈时判断与栈头元素是否一致，如果一致，即这两个元素相同相邻，则需要将栈头元素出栈，并且当前元素也无需入栈

解题步骤： 遍历字符串，取出栈头字符，判断当前字符与栈头字符是否一致

• 不一致，栈头字符进栈，当前字符进栈
• 一致，即栈头字符与当前字符相同相邻，都不需要进栈，直接进入下次遍历即可

遍历完成后，返回栈中字符串

代码实现：

const removeDuplicates = function(S) {
 let stack = []
 for(c of S) {
 let prev = stack.pop()
 if(prev !== c) {
 stack.push(prev)
 stack.push(c)
 }
 }
 return stack.join('')
};

时间复杂度：O(n)

空间复杂度：O(n)

leetcode

[iconWave]

const removeDuplicates = (str) =>{
 if (str.length === 0) return ''
 let newStr = str.slice(0)
 for(let i = 0; i < newStr.length; i++){
 if(newStr[i] === newStr[i + 1]){
 newStr = newStr.replace(/(\w)\1/g, '')
 i === 0 ? (i = i - 1) : (i = i - 2)
 }
 }
 return newStr
}

[qianlongo]

递归加遍历

var removeDuplicates = function(S) {
 if (S.length <= 1) {
 return S
 }

 let left = 0
 let right = left + 1

 while (right < S.length) {
 if (S.charAt(left) === S.charAt(right)) {
 return removeDuplicates(S.slice(0, left) + S.slice(right + 1))
 } else {
 left += 1
 right = left + 1
 }
 }

 return S
};

[qianlongo]

利用栈

var removeDuplicates = function(S) {
 let charStack = []

 for (let s of S) {
 const top = charStack[ charStack.length - 1 ]
 // 相等则把栈顶元素删除，并且当前元素不入栈
 if (s === top) {
 charStack.pop()
 } else {
 charStack.push(s)
 }
 }
 
 return charStack.join('')
};

[qianlongo]

递归 + 正则

var removeDuplicates = function(S) {
 const repeatLenStrRe = /(.)\1/g
 const replaceStr = S.replace(repeatLenStrRe, '')

 if (replaceStr === S) {
 return replaceStr
 } else {
 return removeDuplicates(replaceStr)
 }
};

[lirunkai]

function removeDuplicates(S) {
 let stack = []
 for (let i = 0; i<S.length; i++){
 if (stack.length) {
 if(stack[stack.length - 1] == S[i]) {
 stack.pop()
 } else {
 stack.push(S[i])
 }
 } else{
 stack.push(S[i])
 }
 
 }
 return stack.join('')
}

[laibao101]

var removeDuplicates = function(S) {
 // 第一种方法：使用栈
 const stack = []
 for (const w of S) {
 const cur = stack.pop()
 if (w !== cur) {
 stack.push(cur)
 stack.push(w)
 } 
 }

 return stack.join('')

 // 第二种方法，字符串本身处理
 for (let i = 0; i < S.length;) {
 if (S[i] === S[i + 1]) {
 S = S.slice(0, i) + S.slice(i+2)
 i = 0
 } else {
 i++
 }
 }

 return S
};