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
};