Question

2273. Find Resultant Array After Removing Anagrams

中文文档

Description

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".

 

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.

Solutions

Solution 1

class Solution:
  def removeAnagrams(self, words: List[str]) -> List[str]:
    return [
      w
      for i, w in enumerate(words)
      if i == 0 or sorted(w) != sorted(words[i - 1])
    ]

class Solution {
  public List<String> removeAnagrams(String[] words) {
    List<String> ans = new ArrayList<>();
    String prev = "";
    for (String w : words) {
      char[] cs = w.toCharArray();
      Arrays.sort(cs);
      String t = String.valueOf(cs);
      if (!t.equals(prev)) {
        ans.add(w);
      }
      prev = t;
    }
    return ans;
  }
}

function removeAnagrams(words: string[]): string[] {
  const n = words.length;
  let ans = [];
  ans.push(words[0]);
  let pre = countWord(words[0]).join('');
  for (let i = 1; i < n; i++) {
    let cur = countWord(words[i]).join('');
    if (pre !== cur) {
      ans.push(words[i]);
      pre = cur;
    }
  }
  return ans;
}

function countWord(word: string): number[] {
  let count = new Array(128).fill(0);
  for (let i = 0; i < word.length; i++) {
    count[word.charCodeAt(i)]++;
  }
  return count;
}