跳转至

2514. 统计同位异构字符串数目

题目描述

给你一个字符串 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 <= 105
  • s 只包含小写英文字母和空格 ' ' 。
  • 相邻单词之间由单个空格隔开。

解法

方法一

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
mod = 10**9 + 7
f = [1]
for i in range(1, 10**5 + 1):
    f.append(f[-1] * i % mod)


class Solution:
    def countAnagrams(self, s: str) -> int:
        ans = 1
        for w in s.split():
            cnt = Counter(w)
            ans *= f[len(w)]
            ans %= mod
            for v in cnt.values():
                ans *= pow(f[v], -1, mod)
                ans %= mod
        return ans

 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
27
import java.math.BigInteger;

class Solution {
    private static final int MOD = (int) 1e9 + 7;

    public int countAnagrams(String s) {
        int n = s.length();
        long[] f = new long[n + 1];
        f[0] = 1;
        for (int i = 1; i <= n; ++i) {
            f[i] = f[i - 1] * i % MOD;
        }
        long p = 1;
        for (String w : s.split(" ")) {
            int[] cnt = new int[26];
            for (int i = 0; i < w.length(); ++i) {
                ++cnt[w.charAt(i) - 'a'];
            }
            p = p * f[w.length()] % MOD;
            for (int v : cnt) {
                p = p * BigInteger.valueOf(f[v]).modInverse(BigInteger.valueOf(MOD)).intValue()
                    % MOD;
            }
        }
        return (int) p;
    }
}

 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
27
28
29
class Solution {
public:
    const int mod = 1e9 + 7;

    int countAnagrams(string s) {
        stringstream ss(s);
        string w;
        long ans = 1, mul = 1;
        while (ss >> w) {
            int cnt[26] = {0};
            for (int i = 1; i <= w.size(); ++i) {
                int c = w[i - 1] - 'a';
                ++cnt[c];
                ans = ans * i % mod;
                mul = mul * cnt[c] % mod;
            }
        }
        return ans * pow(mul, mod - 2) % mod;
    }

    long pow(long x, int n) {
        long res = 1L;
        for (; n; n /= 2) {
            if (n % 2) res = res * x % mod;
            x = x * x % mod;
        }
        return res;
    }
};

 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
const mod int = 1e9 + 7

func countAnagrams(s string) int {
    ans, mul := 1, 1
    for _, w := range strings.Split(s, " ") {
        cnt := [26]int{}
        for i, c := range w {
            i++
            cnt[c-'a']++
            ans = ans * i % mod
            mul = mul * cnt[c-'a'] % mod
        }
    }
    return ans * pow(mul, mod-2) % mod
}

func pow(x, n int) int {
    res := 1
    for ; n > 0; n >>= 1 {
        if n&1 > 0 {
            res = res * x % mod
        }
        x = x * x % mod
    }
    return res
}

方法二

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
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

评论