What is the optimal way to check if two words are anagrams?

The most efficient way to check for anagrams is to use a frequency count of characters or to sort both strings and compare them.

How does this problem relate to the Array, Hash Table, and String topics?

This problem involves scanning through an array, using a hash table to store character frequencies or sorted versions of words, and dealing with strings in the process.

Can this problem be solved in-place?

Yes, it can be solved in-place by modifying the input array as you process the elements.

What is the time complexity of this problem?

The time complexity depends on the approach. Sorting each word would result in O(n * k log k), where n is the number of words and k is the length of the words. The hash map approach can be more efficient with a time complexity of O(n * k).

What are the common mistakes in solving this problem?

Common mistakes include failing to check for adjacent anagrams properly, overcomplicating the solution with unnecessary sorting, or not considering edge cases.

#2273

Easy

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

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

给你一个下标从 0 开始的字符串数组 words ，其中 words[i] 由小写英文字符组成。在一步操作中，需要选出任一下标 i ，从 words 中删除 words[i] 。其中下标 i 需要同时满足下述两个条件： 0 words[i - 1] 和 words[i] 是字母异位词。只要…

数组哈希表字符串排序

题目描述

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

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

0 < i < words.length
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] 由小写英文字母组成

lightbulb

解题思路

方法一：模拟

我们首先将 $\textit{words}[0]$ 加入答案数组，然后从 $\textit{words}[1]$ 开始遍历，如果 $\textit{words}[i - 1]$ 和 $\textit{words}[i]$ 不是字母异位词，我们就将 $\textit{words}[i]$ 加入答案数组。

问题转换为判断两个字符串是否是字母异位词，我们定义一个辅助函数 $\textit{check}(s, t)$ 来实现这个功能。如果 $s$ 和 $t$ 不是字母异位词，我们就返回 $\text{true}$ ，否则返回 $\text{false}$ 。

在函数 $\textit{check}(s, t)$ 中，我们首先判断 $s$ 和 $t$ 的长度是否相等，如果不相等，我们就返回 $\text{true}$ 。否则，我们用一个长度为 $26$ 的数组 $\textit{cnt}$ 来统计 $s$ 中每个字符出现的次数，然后遍历 $t$ 中的每个字符，将 $\textit{cnt}[c]$ 减 $1$ ，如果 $\textit{cnt}[c]$ 小于 $0$ ，我们就返回 $\text{true}$ 。如果正常遍历完 $t$ 中的每个字符，说明 $s$ 和 $t$ 是字母异位词，我们返回 $\text{false}$ 。

时间复杂度 $O(L)$ ，空间复杂度 $O(|\Sigma|)$ 。其中 $L$ 是数组 $\textit{words}$ 的长度，而 $\Sigma$ 是字符集，这里是小写英文字母，所以 $|\Sigma| = 26$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

class Solution:
    def removeAnagrams(self, words: List[str]) -> List[str]:
        def check(s: str, t: str) -> bool:
            if len(s) != len(t):
                return True
            cnt = Counter(s)
            for c in t:
                cnt[c] -= 1
                if cnt[c] < 0:
                    return True
            return False

        return [words[0]] + [t for s, t in pairwise(words) if check(s, t)]

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Understanding of array scanning techniques and hash map usage.
question_mark
Efficiency in detecting anagrams using frequency counts or sorting.
question_mark
Ability to optimize for space and time complexity while solving.

warning

常见陷阱

外企场景

error
Failing to recognize the need for an efficient anagram check (sorting or hash map).
error
Not handling edge cases, like when no words are anagrams.
error
Overcomplicating the solution with unnecessary operations or data structures.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Allowing for a custom comparator instead of using frequency counts.
arrow_right_alt
Modifying the input in place without using extra space.
arrow_right_alt
Handling case sensitivity or extending the problem to a larger character set.

help

常见问题

外企场景

继续练习

#2135 统计追加字母可以获得的单词数 #2418 按身高排序 #2456 最流行的视频创作者