[LeetCode] Find Resultant Array After Removing Anagrams

1.문제

You are given a 0-indexed string array words, where words[i] consists of lowercase English letters.

In one operation, select any index i such that 0 < i < words.length and words[i - 1] and words[i] are anagrams, and delete words[i] from words. Keep performing this operation as long as you can select an index that satisfies the conditions.

Return words after performing all operations. It can be shown that selecting the indices for each operation in any arbitrary order will lead to the same result.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase using all the original letters exactly once. For example, "dacb" is an anagram of "abdc".

문자열 배열 words가 주어질 때 0 < i < words.length 범위의 index 중 words[i-1] 과 words[i] 가 anagram이면 words[i]를 삭제한다.

이러한 과정을 끝까지 행했을 때 남아있는 단어들의 배열을 리턴하는 문제이다.

Example 1

Input: words = ["abba","baba","bbaa","cd","cd"]
Output: ["abba","cd"]
Explanation:
One of the ways we can obtain the resultant array is by using the following operations:
- Since words[2] = "bbaa" and words[1] = "baba" are anagrams, we choose index 2 and delete words[2].
  Now words = ["abba","baba","cd","cd"].
- Since words[1] = "baba" and words[0] = "abba" are anagrams, we choose index 1 and delete words[1].
  Now words = ["abba","cd","cd"].
- Since words[2] = "cd" and words[1] = "cd" are anagrams, we choose index 2 and delete words[2].
  Now words = ["abba","cd"].
We can no longer perform any operations, so ["abba","cd"] is the final answer.

Example 2

Input: words = ["a","b","c","d","e"]
Output: ["a","b","c","d","e"]
Explanation:
No two adjacent strings in words are anagrams of each other, so no operations are performed.

Constraints:

• 1 <= words.length <= 100
• 1 <= words[i].length <= 10
• words[i] consists of lowercase English letters.

2.풀이

1. 배열의 앞 단어부터 스택에 넣는다.
2. 다음 단어와 스택의 top 단어를 비교한다.
3. anagram이 아니면 stack에 현재 단어를 넣어준다.

/**
 * @param {string[]} words
 * @return {string[]}
 */
const removeAnagrams = function (words) {
  // 가장 앞의 단어 정렬해서 stack에 넣기
  const stack = [words[0].split("").join("")];

  let top = "";
  let current = "";
  for (let i = 1; i < words.length; i++) {
    // 스택의 가장 위에있는 요소를 꺼낸다
    top = stack[stack.length - 1];
    // 현재 단어를 오름차순으로 정렬한다
    current = words[i].split("").sort().join("");
    // 스택의 가장 위부분과 current 를 비교한다
    if (top.split("").sort().join("") === current) {
      continue;
    } else {
      // 만약 다르다면 current 단어를 stack에 넣어준다
      stack.push(words[i]);
    }
  }

  return stack;
};

3.결과