coding test/leetCode

[leetCode/JS] 1047. Remove All Adjacent Duplicates In String

쭘봉 2022. 11. 22. 21:01

문제 설명

You are given a string s consisting of lowercase English 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 can be proven that the answer is unique.

입출력 예

Example 1:

  • Input: s = "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".

Example 2:

  • Input: s = "azxxzy"
  • Output: "ay"

Constraints

1 <= s.length <= 10^5
s consists of lowercase English letters.


내 솔루션

  • 전체 반복 중 앞뒤로 중복된 글자를 만나면 삭제하고 i를 -1하여 검사한다.
  • 메모리 사용량, 속도에서 아슬아슬하게 통과ㅋ slice 말고 array 변환 후 반복했으면 좀 나았을까
var removeDuplicates = function(s) {
    let str = s;
    for(let i = 0; i < str.length; i++) {
        if(str[i] === str[i+1]){
          str = str.slice(0,i) + str.slice(i+2);
          i = i - 2 < 0 ? -1 : i - 2;
        }
    }
    return str;
};

최고의 솔루션

  • 현재와 이전 글자를 비교하여 삭제 해야 하기 때문에 Stack으로 접근한 듯.
  • 이쁘고 깔끔, 속도와 메모리도 빠르고 가볍다.
var removeDuplicates = function(S) {
    let res = [];
    for(let i=0; i<S.length; i++){
        if(S[i] !== res[res.length-1]) {
            res.push(S[i]);
        } else {
            res.pop();
        }
    }
    return res.join("");
};

감상평

  • 가벼운 마음에 첫 leetcode를 풀고 통과해 뿌듯! 하지만 세상엔 똑똑이들이 많다는 것을 다시 한 번 실감.