Easy

题目描述

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

在一步操作中，需要选择任意下标 i，满足 0 < i < words.length 且 words[i - 1] 和 words[i] 是 字母异位词，并删除 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] 由小写英文字母组成

解题思路

这道题要求我们移除与前一个元素构成字母异位词的元素。关键在于理解操作的本质：只要当前字符串与前面某个保留的字符串是字母异位词，就要删除当前字符串。

解题思路

有两种主要思路：

方法一：模拟删除过程

遍历数组，如果当前字符串与前一个字符串是字母异位词，就删除当前字符串。重复这个过程直到无法再删除。

方法二：一次遍历（推荐）

关键观察：如果 words[i] 与 words[i-1] 是字母异位词，那么 words[i] 最终会被删除。我们可以一次遍历，只保留那些与前一个保留元素不是字母异位词的字符串。

判断两个字符串是否为字母异位词的方法：

  1. 排序后比较是否相等
  2. 统计字符频率后比较

排序方法更简洁，在字符串长度不大的情况下效率也很好。

算法步骤

  1. 将第一个字符串加入结果数组
  2. 从第二个字符串开始遍历
  3. 将当前字符串排序后与结果数组最后一个字符串排序后比较
  4. 如果不相等（不是字母异位词），将当前字符串加入结果数组
  5. 返回结果数组

代码实现

class Solution {
public:
    vector<string> removeAnagrams(vector<string>& words) {
        vector<string> result;
        result.push_back(words[0]);
        
        for (int i = 1; i < words.size(); i++) {
            string curr = words[i];
            string prev = result.back();
            
            sort(curr.begin(), curr.end());
            sort(prev.begin(), prev.end());
            
            if (curr != prev) {
                result.push_back(words[i]);
            }
        }
        
        return result;
    }
};

class Solution:
    def removeAnagrams(self, words: List[str]) -> List[str]:
        result = [words[0]]
        
        for i in range(1, len(words)):
            curr_sorted = ''.join(sorted(words[i]))
            prev_sorted = ''.join(sorted(result[-1]))
            
            if curr_sorted != prev_sorted:
                result.append(words[i])
        
        return result

public class Solution {
    public IList<string> RemoveAnagrams(string[] words) {
        List<string> result = new List<string>();
        result.Add(words[0]);
        
        for (int i = 1; i < words.Length; i++) {
            char[] curr = words[i].ToCharArray();
            char[] prev = result[result.Count - 1].ToCharArray();
            
            Array.Sort(curr);
            Array.Sort(prev);
            
            if (!new string(curr).Equals(new string(prev))) {
                result.Add(words[i]);
            }
        }
        
        return result;
    }
}

var removeAnagrams = function(words) {
    const result = [words[0]];
    
    for (let i = 1; i < words.length; i++) {
        const currSorted = words[i].split('').sort().join('');
        const prevSorted = result[result.length - 1].split('').sort().join('');
        
        if (currSorted !== prevSorted) {
            result.push(words[i]);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × m × log m)n 是数组长度，m 是字符串平均长度，每次排序需要 O(m log m)
空间复杂度O(n × m)结果数组最多包含 n 个字符串，每个字符串长度为 m

相关题目