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

🟢   🔖  数组 哈希表 字符串 排序  🔗 力扣 LeetCode

题目

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.

题目大意

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

解题思路

1. 构造字符频率特征值：

   • 使用一个长度为 26 的数组表示每个字母出现的次数。
   • 对字符串进行遍历，根据字符的 ASCII 值计算其在频率数组中的位置，并累加频率。
   • 将频率数组转换成字符串作为单词的特征值。

2. 遍历数组：

   • 维护一个变量 prev 存储上一个单词的特征值。
   • 从第 1 个单词开始与 prev 比较：
     • 如果特征值相同，说明当前单词是字谜词，将其置为空字符串。
     • 如果特征值不同，更新 prev，继续处理。

3. 过滤结果：

   • 使用 filter 方法去除空字符串，保留非字谜词。

复杂度分析

• 时间复杂度：O(m * n)

  • 计算字符串的特征值 O(m * n)，其中m 是数组长度，n 是数组中字符串的平均字符数。
  • 遍历数组进行比较 O(m)，其中 m 是数组长度。
  • 总时间复杂度为 O(m * n + m) ≈ O(m * n)。

• 空间复杂度：O(1)，使用一个固定大小的数组 arr，空间复杂度为 O(26) ≈ O(1)。

代码

/**
 * @param {string[]} words
 * @return {string[]}
 */
var removeAnagrams = function (words) {
	// 将字符串转换为特征值（字符频率数组的字符串形式）
	const countChar = (str) => {
		let arr = new Array(26).fill(0); // 用于统计字母频率
		for (let char of str) {
			arr[char.charCodeAt() - 97]++;
		}
		return arr.join('');
	};

	let prev = countChar(words[0]); // 初始特征值

	for (let i = 1; i < words.length; i++) {
		const cur = countChar(words[i]); // 当前字符串的特征值
		if (prev === cur) {
			words[i] = ''; // 如果是字谜词，将其标记为空
		} else {
			prev = cur; // 更新特征值
		}
	}

	// 过滤掉空字符串
	return words.filter((word) => word !== '');
};

相关题目

题号	标题	题解	标签	难度	力扣
49	字母异位词分组	[✓]	数组 哈希表 字符串 1+	🟠	🀄️ 🔗
242	有效的字母异位词	[✓]	哈希表 字符串 排序	🟢	🀄️ 🔗