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

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

给你一个下标从 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] 由小写英文字母组成

方法一：逐个判断

思路与算法

由于「字母异位词」具有等价性和传递性，因此对于 words 中出现的多个连续字母异位词，我们只需要保留最前面的即可。

因此，我们可以采用如下的方式实现移除操作：

我们用 res 来表示结果数组，res 中初始含有 words}[0]。我们按顺序遍历 words 的剩余单词，每当遍历到一个新的单词时，我们检查该单词与 words 中它的前一个单词是否为字母异位词：如果是，则该单词需要被删除，我们不进行任何操作；反之则将该单词添加至 res 末尾。

关于如何判断两个单词 word}_1 与 word}_2 是否为字母异位词，我们用函数 compare}(\textit{word}_1, \textit{word}_2) 实现判断。具体地，我们用长度为英文字符数量（26）的频率数组 freq 统计每个字符的出现次数，当我们遍历 word}_1 的每个字符时，我们将 freq 对应下标的元素加上 1；当我们遍历 word}_2 的每个字符时，我们将 freq 对应下标的元素减去 1。最终，如果 freq 数组的全部元素均为 0，则说明两个单词为字母异位词，我们返回 true；反之则不是，我们返回 false。

最终 res 即为移除字母异位词之后的结果数组，我们返回该数组作为答案即可。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    vector<string> removeAnagrams(vector<string>& words) {
        vector<string> res = {words[0]};   // 结果数组
        int n = words.size();
        // 判断两个单词是否为字母异位词
        auto compare = [](const string& word1, const string& word2) -> bool {
            vector<int> freq(26);
            for (char ch: word1) {
                ++freq[ch-'a'];
            }
            for (char ch: word2) {
                --freq[ch-'a'];
            }
            return all_of(freq.begin(), freq.end(), [](int x) { return x == 0; });
        };

        for (int i = 1; i < n; ++i) {
            if (compare(words[i], words[i-1])) {
                continue;
            }
            res.push_back(words[i]);
        }
        return res;
    }
};
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def removeAnagrams(self, words: List[str]) -> List[str]:
        res = [words[0]]   # 结果数组
        n = len(words)
        # 判断两个单词是否为字母异位词
        def compare(word1: str, word2: str) -> bool:
            freq = [0] * 26
            for ch in word1:
                freq[ord(ch)-ord('a')] += 1
            for ch in word2:
                freq[ord(ch)-ord('a')] -= 1
            return all(x == 0 for x in freq)
        
        for i in range(1, n):
            if compare(words[i], words[i-1]):
                continue
            res.append(words[i])
        return res

复杂度分析

  • 时间复杂度：O(mn)，其中 n 为 words 的长度, m 为 words 中单词的长度。即为遍历 words 数组并判断每个元素是否需要移除的时间复杂度。

  • 空间复杂度：O(|\Sigma|)，其中 |\Sigma| 为字符集的大小。即为字符出现次数数组的空间开销。

 Comments
On this page
2273-移除字母异位词后的结果数组