LeetCode 题解工作台
统计同位异构字符串数目
给你一个字符串 s ，它包含一个或者多个单词。单词之间用单个空格 ' ' 隔开。 如果字符串 t 中第 i 个单词是 s 中第 i 个单词的一个 排列 ，那么我们称字符串 t 是字符串 s 的同位异构字符串。 比方说， "acb dfe" 是 "abc def" 的同位异构字符串，但是 "def c…
5
题型
4
代码语言
3
相关题
当前训练重点
困难 · 哈希·数学
答案摘要
class Solution: def countAnagrams(self, s: str) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 哈希·数学 题型思路
题目描述
给你一个字符串 s ，它包含一个或者多个单词。单词之间用单个空格 ' ' 隔开。
如果字符串 t 中第 i 个单词是 s 中第 i 个单词的一个 排列 ，那么我们称字符串 t 是字符串 s 的同位异构字符串。
- 比方说，
"acb dfe"是"abc def"的同位异构字符串，但是"def cab"和"adc bef"不是。
请你返回 s 的同位异构字符串的数目，由于答案可能很大，请你将它对 109 + 7 取余 后返回。
示例 1：
输入：s = "too hot" 输出：18 解释：输入字符串的一些同位异构字符串为 "too hot" ，"oot hot" ，"oto toh" ，"too toh" 以及 "too oht" 。
示例 2：
输入：s = "aa" 输出：1 解释：输入字符串只有一个同位异构字符串。
提示：
1 <= s.length <= 105s只包含小写英文字母和空格' '。- 相邻单词之间由单个空格隔开。
解题思路
方法一
class Solution:
def countAnagrams(self, s: str) -> int:
mod = 10**9 + 7
ans = mul = 1
for w in s.split():
cnt = Counter()
for i, c in enumerate(w, 1):
cnt[c] += 1
mul = mul * cnt[c] % mod
ans = ans * i % mod
return ans * pow(mul, -1, mod) % mod
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity depends on computing factorials and iterating over each character in all words, typically O(n + sum(word lengths)) where n is string length. Space complexity is O(k) per word for character counts, with k up to 26 for lowercase letters. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Emphasize efficient counting over generating all permutations.
- question_mark
Check if the candidate handles repeated characters correctly with combinatorial formulas.
- question_mark
Look for proper use of modulo arithmetic to avoid integer overflow.
常见陷阱
外企场景- error
Attempting to generate all permutations explicitly, which causes TLE for long strings.
- error
Ignoring repeated letters and overcounting identical permutations.
- error
Multiplying large factorials without modulo, causing overflow.
进阶变体
外企场景- arrow_right_alt
Count anagrams of a single long word with repeated characters.
- arrow_right_alt
Compute anagrams where only a subset of words can be permuted.
- arrow_right_alt
Find the lexicographically smallest or largest anagram instead of the count.