移除字母异位词后的结果数组

标签: 数组 哈希表 字符串 排序

难度: Easy

给你一个下标从 0 开始的字符串 words ，其中 words[i] 由小写英文字符组成。

在一步操作中，需要选出任一下标 i ，从 words 中 删除 words[i] 。其中下标 i 需要同时满足下述两个条件：

  1. 0 < i < words.length
  2. words[i - 1] 和 words[i] 是 字母异位词 。

只要可以选出满足条件的下标，就一直执行这个操作。

在执行所有操作后，返回 words 。可以证明，按任意顺序为每步操作选择下标都会得到相同的结果。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。例如，"dacb" 是 "abdc" 的一个字母异位词。

示例 1：

输入：words = ["abba","baba","bbaa","cd","cd"]
输出：["abba","cd"]
解释：
获取结果数组的方法之一是执行下述步骤：
- 由于 words[2] = "bbaa" 和 words[1] = "baba" 是字母异位词，选择下标 2 并删除 words[2] 。
  现在 words = ["abba","baba","cd","cd"] 。
- 由于 words[1] = "baba" 和 words[0] = "abba" 是字母异位词，选择下标 1 并删除 words[1] 。
  现在 words = ["abba","cd","cd"] 。
- 由于 words[2] = "cd" 和 words[1] = "cd" 是字母异位词，选择下标 2 并删除 words[2] 。
  现在 words = ["abba","cd"] 。
无法再执行任何操作，所以 ["abba","cd"] 是最终答案。

示例 2：

输入：words = ["a","b","c","d","e"]
输出：["a","b","c","d","e"]
解释：
words 中不存在互为字母异位词的两个相邻字符串，所以无需执行任何操作。

提示：

  • 1 <= words.length <= 100
  • 1 <= words[i].length <= 10
  • words[i] 由小写英文字母组成

Submission

运行时间: 33 ms

内存: 16.0 MB

class Solution:
    def removeAnagrams(self, words: List[str]) -> List[str]:
        
        # 判断两个字符串是否互为字母异位词
        def isAnagram(s1, s2):
            return sorted(s1) == sorted(s2)

        i = 1  # 从第二个元素开始遍历
        while i < len(words):
            # 如果当前元素和前一个元素互为字母异位词，则删除当前元素
            if isAnagram(words[i], words[i - 1]):
                words.pop(i)
            else:
                i += 1  # 否则，移动到下一个元素
        return words

Explain

The solution iterates through the list of words starting from the second element. For each word, it checks if it is an anagram of the previous word using a helper function 'isAnagram' that compares the sorted versions of the two strings. If the current word is an anagram of the previous one, it is removed from the list. Otherwise, the iterator moves to the next word. This process continues until the end of the list is reached.

时间复杂度: O(n * k log k)

空间复杂度: O(1)

class Solution:
    def removeAnagrams(self, words: List[str]) -> List[str]:
        
        # 判断两个字符串是否互为字母异位词
        def isAnagram(s1, s2):
            return sorted(s1) == sorted(s2)

        i = 1  # 从第二个元素开始遍历
        while i < len(words):
            # 如果当前元素和前一个元素互为字母异位词，则删除当前元素
            if isAnagram(words[i], words[i - 1]):
                words.pop(i)
            else:
                i += 1  # 否则，移动到下一个元素
        return words

Explore

在我的算法中，如果连续多个词都是互为字母异位词，将会连续删除直到遇到不是字母异位词的词为止。这是通过在循环中不递增索引`i`来实现的，除非当前词和前一个词不是字母异位词。因此，只要当前词是前一个词的字母异位词，就会将其删除，连续进行，直到遇见一个不是字母异位词的词。

除了排序，还可以使用字符计数的方法来判断两个字符串是否为字母异位词。具体方法是使用一个固定大小为26的整数数组（假设输入字符串只包含小写字母）来计数每个字符的出现次数。遍历第一个字符串增加计数，遍历第二个字符串减少计数。最后检查这个数组中的所有值是否都为零。这种方法的时间复杂度为O(n)，通常比排序方法的O(n log n)更高效。

我的算法可以正确处理`words`数组为空或只有一个元素的情况。如果数组为空，循环不会执行任何操作，返回空数组；如果数组只有一个元素，由于从第二个元素开始遍历，循环同样不会执行，直接返回原数组。因此，不需要添加特殊逻辑来处理这些边界情况。

这个描述可能是一个误解。实际上，在我的算法中，操作的顺序是从前往后的，且这种顺序对最终结果是有影响的。算法设计确实依赖于这种顺序以确保正确删除所有连续的字母异位词。因此，这不仅仅是一个观察结果，而是算法设计中特意使用的一个属性。