[LeetCode] Remove All Adjacent Duplicates In String

1.문제

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.

문자열 s 가 주어질 때 s중 인접한 두개의 철자가 같으면 지우는 과정을 인접한 중복된 철자가 없을 때 까지 진행한다고 한다. 위 과정을 진행하고 난 뒤의 문자열을 리턴하는 문제이다.

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.

2.풀이

1. 스택에 먼저 s의 제일 앞 철자를 넣는다.
2. 반복문을 돌면서 현재 철자를 체크하는데 만약 stack의 가장 위에 있는 철자랑 같으면 스택에서 없앤다.

/**
 * @param {string} s
 * @return {string}
 */
const removeDuplicates = function (s) {
  const stack = [s[0]]; // 문자열의 가장 앞 철자를 스택에 넣는다

  for (let i = 1; i < s.length; i++) {
    let top = stack.pop(); // 스택의 가장 윗부분을 하나 뺀다
    if (top !== s[i]) {
      // 스택의 가장 윗부분과 현재 철자가 다르면 먼저 뺐던 가장 위 철자와 현재 철자를 순서대로 스택에 쌓는다
      stack.push(top);
      stack.push(s[i]);
    }
  }

  return stack.join("");
};

3.결과