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

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

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

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

示例：

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

提示：

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

附leetcode地址：leetcode

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

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)

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

解题思路：
新建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)

@fanefanes

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

@fanefanes

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

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

@fanefanes

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

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

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

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('')
};

解法：利用栈

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

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

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

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

代码实现：

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

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
}

递归加遍历

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

利用栈

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('')
};

递归 + 正则

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

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

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('')
}

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

比较简单的题，用栈处理

var removeDuplicates = function(S) {
    let res = [];
    for (c of S) {
        if (res.length > 0 && res[res.length-1] == c) {
            res.pop();
        } else {
            res.push(c);
        }
    }
    return res.join('');
};

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

利用栈

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

利用栈存储以扫描过的字符，每次读取字符的时候都会跟栈顶元素进行比较，如果相同就推出栈顶元素，否则字符入栈

const removeDuplicates = (source: string) => {
    if (source.length <= 1) return source;
    const stack: string[] = [];
    for (let i = 0; i < source.length; i++) {
        const char = source.charAt(i);
        if (stack.length > 0 && char === stack[stack.length - 1]) {
            stack.pop();
            continue;
        }
        stack.push(char);
    }
    return stack.join('');
};

function removeDuplicates(srt) {
  const reg = /(\w)\1+/g;
  const srt2 = srt.replace(reg, "");
  if (srt !== srt2) return removeDuplicates(srt2);
  return srt2;
}

function deleteNearChar(str){
    function deleteChar(str){
        let k = 0
        while(k<str.length-1){
            if(str.charAt(k)===str.charAt(k+1)){
                let c = str.charAt(k)
                while(c === str.charAt(k)){
                    let list = str.split('')
                    list.splice(k,1)
                    str = list.join('')
                }
            }else{
                k++
            }
           
        }
        return str
    }
    function isNearRepeat(str){
        let list = str.split('')
        return list.some((it,idx)=>list[idx]===list[idx+1])
    }

    while(isNearRepeat(str)){
        str = deleteChar(str)
    }
    return str
} 

console.log(deleteNearChar('abbaca'))

Navigation Menu

Repository navigation

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

解法：利用栈

递归加遍历

利用栈

递归 + 正则

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

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

Description

Activity

Makus577 commented on Apr 24, 2020

7777sea commented on Apr 24, 2020

fanefanes commented on Apr 24, 2020

thxiami commented on Apr 24, 2020

fanefanes commented on Apr 24, 2020

thxiami commented on Apr 24, 2020

wufeicris commented on Apr 24, 2020

sisterAn commented on Apr 24, 2020

解法：利用栈

iconWave commented on May 29, 2020

qianlongo commented on Aug 22, 2020

递归加遍历

qianlongo commented on Aug 22, 2020

利用栈

qianlongo commented on Aug 22, 2020

递归 + 正则

lirunkai commented on Sep 15, 2020

laibao101 commented on Oct 4, 2020

dinjufen commented on Oct 14, 2020

AnranS commented on Nov 19, 2020

lewisYe commented on Apr 9, 2021

JohnApache commented on Apr 29, 2021

zhw2590582 commented on Sep 29, 2021

AlexZhang11 commented on May 31, 2024

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions