Hard

题目描述

给你一个字符串 s ，它包含一个或者多个单词。单词之间用单个空格 ' ' 分隔。

如果字符串 t 中第 i 个单词是字符串 s 中第 i 个单词的一个 字母异位词 ，那么字符串 t 就是字符串 s 的字母异位词。

  • 举个例子，"acb dfe" 是 "abc def" 的字母异位词，但是 "def cab" 和 "adc bef" 不是。

请你返回 s 的字母异位词的数目。由于答案可能很大，请你将它对 10^9 + 7 取余 后返回。

示例 1：

输入：s = "too hot"
输出：18
解释：输入字符串的一些字母异位词为 "too hot", "oot hot", "oto toh", "too toh" 和 "too oht" 。

示例 2：

输入：s = "aa"
输出：1
解释：输入字符串只有一个字母异位词。

提示：

  • 1 <= s.length <= 10^5
  • s 只包含小写英文字母和空格 ' ' 。
  • 相邻单词之间由单个空格分隔。

解题思路

解题思路

这道题要求计算字符串的字母异位词数量，核心思想是利用排列组合中的多重排列公式。

分析过程：

  1. 单词独立性：由于每个单词的字母异位词只能在对应位置形成，所以各单词的字母异位词数量可以独立计算，最终结果是所有单词字母异位词数量的乘积。

  2. 多重排列计算：对于每个单词，如果所有字符都不相同，排列数就是 n!。但当有重复字符时，需要使用多重排列公式：n! / (c1! × c2! × ... × ck!)，其中 ci 是第 i 种字符的出现次数。

  3. 算法步骤：

    • 将字符串按空格分割成单词
    • 对每个单词统计字符频率
    • 计算该单词的排列数：len! / (freq1! × freq2! × ...)
    • 将所有单词的排列数相乘

  4. 优化技巧：由于需要计算阶乘和取模运算，可以预计算阶乘数组和逆元，避免重复计算。对于除法取模，使用费马小定理：a/b ≡ a × b^(p-2) (mod p)。

时间复杂度：O(n)，其中 n 是字符串长度 空间复杂度：O(n)，用于存储阶乘数组

代码实现

class Solution {
public:
    int countAnagrams(string s) {
        const int MOD = 1e9 + 7;
        vector<long long> fact(100001);
        fact[0] = 1;
        for (int i = 1; i <= 100000; i++) {
            fact[i] = fact[i-1] * i % MOD;
        }
        
        auto power = [&](long long a, long long b) -> long long {
            long long res = 1;
            while (b > 0) {
                if (b & 1) res = res * a % MOD;
                a = a * a % MOD;
                b >>= 1;
            }
            return res;
        };
        
        auto inv = [&](long long a) -> long long {
            return power(a, MOD - 2);
        };
        
        long long result = 1;
        stringstream ss(s);
        string word;
        
        while (ss >> word) {
            vector<int> freq(26, 0);
            for (char c : word) {
                freq[c - 'a']++;
            }
            
            long long permutations = fact[word.length()];
            for (int f : freq) {
                if (f > 1) {
                    permutations = permutations * inv(fact[f]) % MOD;
                }
            }
            
            result = result * permutations % MOD;
        }
        
        return result;
    }
};

class Solution:
    def countAnagrams(self, s: str) -> int:
        MOD = 10**9 + 7
        
        # Precompute factorials
        fact = [1] * 100001
        for i in range(1, 100001):
            fact[i] = fact[i-1] * i % MOD
        
        def pow_mod(a, b):
            res = 1
            while b > 0:
                if b & 1:
                    res = res * a % MOD
                a = a * a % MOD
                b >>= 1
            return res
        
        def inv(a):
            return pow_mod(a, MOD - 2)
        
        result = 1
        words = s.split()
        
        for word in words:
            freq = {}
            for char in word:
                freq[char] = freq.get(char, 0) + 1
            
            permutations = fact[len(word)]
            for count in freq.values():
                if count > 1:
                    permutations = permutations * inv(fact[count]) % MOD
            
            result = result * permutations % MOD
        
        return result

public class Solution {
    public int CountAnagrams(string s) {
        const int MOD = 1000000007;
        long[] fact = new long[100001];
        fact[0] = 1;
        for (int i = 1; i <= 100000; i++) {
            fact[i] = fact[i-1] * i % MOD;
        }
        
        long PowerMod(long a, long b) {
            long res = 1;
            while (b > 0) {
                if ((b & 1) == 1) res = res * a % MOD;
                a = a * a % MOD;
                b >>= 1;
            }
            return res;
        }
        
        long Inv(long a) {
            return PowerMod(a, MOD - 2);
        }
        
        long result = 1;
        string[] words = s.Split(' ');
        
        foreach (string word in words) {
            int[] freq = new int[26];
            foreach (char c in word) {
                freq[c - 'a']++;
            }
            
            long permutations = fact[word.Length];
            foreach (int f in freq) {
                if (f > 1) {
                    permutations = permutations * Inv(fact[f]) % MOD;
                }
            }
            
            result = result * permutations % MOD;
        }
        
        return (int)result;
    }
}

var countAnagrams = function(s) {
    const MOD = 1e9 + 7;
    const fact = new Array(100001);
    fact[0] = 1;
    for (let i = 1; i <= 100000; i++) {
        fact[i] = fact[i-1] * i % MOD;
    }
    
    function powerMod(a, b) {
        let res = 1;
        while (b > 0) {
            if (b & 1) res = res * a % MOD;
            a = a * a % MOD;
            b = Math.floor(b / 2);
        }
        return res;
    }
    
    function inv(a) {
        return powerMod(a, MOD - 2);
    }
    
    let result = 1;
    const words = s.split(' ');
    
    for (const word of words) {
        const freq = {};
        for (const char of word) {
            freq[char] = (freq[char] || 0) + 1;
        }
        
        let permutations = fact[word.length];
        for (const count of Object.values(freq)) {
            if (count > 1) {
                permutations = permutations * inv(fact[count]) % MOD;
            }
        }
        
        result = result * permutations % MOD;
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n)
空间复杂度O(n)

其中 n 是字符串的总长度。时间复杂度主要来自于遍历字符串和计算每个单词的字符频率，空间复杂度主要用于存储预计算的阶乘数组。

相关题目