class Solution {
public:
int countAnagrams(string s) {
}
};
6276. 统计同位异构字符串数目
给你一个字符串 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 只包含小写英文字母和空格 ' ' 。原站题解
python3 解法, 执行用时: 260 ms, 内存消耗: 16 MB, 提交时间: 2022-12-25 12:08:02
MOD = 10 ** 9 + 7
class Solution:
def countAnagrams(self, s: str) -> int:
ans = 1
for word in s.split():
n = len(word)
for v in Counter(word).values():
ans *= comb(n, v)
ans %= MOD
n -= v
return ans
golang 解法, 执行用时: 8 ms, 内存消耗: 5.6 MB, 提交时间: 2022-12-25 12:07:10
const mod int = 1e9 + 7
func countAnagrams(s string) int {
ans, mul := 1, 1
for _, s := range strings.Split(s, " ") {
cnt := [26]int{}
for i, c := range s {
cnt[c-'a']++
mul = mul * cnt[c-'a'] % mod
ans = ans * (i + 1) % 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
}
cpp 解法, 执行用时: 20 ms, 内存消耗: 8.8 MB, 提交时间: 2022-12-25 12:06:50
class Solution {
const int MOD = 1e9 + 7;
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;
}
public:
int countAnagrams(string &s) {
long ans = 1L, mul = 1L;
int cnt[26]{};
for (int i = 0, j = 0; i < s.length(); ++i) {
if (s[i] == ' ') {
memset(cnt, 0, sizeof(cnt));
j = 0;
} else {
mul = mul * ++cnt[s[i] - 'a'] % MOD;
ans = ans * ++j % MOD;
}
}
return ans * pow(mul, MOD - 2) % MOD;
}
};
java 解法, 执行用时: 8 ms, 内存消耗: 42.6 MB, 提交时间: 2022-12-25 12:06:31
class Solution {
private static final int MOD = (int) 1e9 + 7;
public int countAnagrams(String S) {
var s = S.toCharArray();
long ans = 1L, mul = 1L;
var cnt = new int[26];
for (int i = 0, j = 0; i < s.length; ++i) {
if (s[i] == ' ') {
Arrays.fill(cnt, 0);
j = 0;
} else {
mul = mul * ++cnt[s[i] - 'a'] % MOD;
ans = ans * ++j % MOD;
}
}
return (int) (ans * pow(mul, MOD - 2) % MOD);
}
private long pow(long x, int n) {
var res = 1L;
for (; n > 0; n /= 2) {
if (n % 2 > 0) res = res * x % MOD;
x = x * x % MOD;
}
return res;
}
}
python3 解法, 执行用时: 304 ms, 内存消耗: 15.9 MB, 提交时间: 2022-12-25 12:06:10
class Solution:
def countAnagrams(self, s: str) -> int:
MOD = 10 ** 9 + 7
ans = mul = 1
for s in s.split():
cnt = Counter()
for i, c in enumerate(s, 1):
cnt[c] += 1
mul = mul * cnt[c] % MOD
ans = ans * i % MOD
return ans * pow(mul, -1, MOD) % MOD