| comments | difficulty | edit_url | rating | source | tags | |||||
|---|---|---|---|---|---|---|---|---|---|---|
true |
困难 |
2069 |
第 94 场双周赛 Q4 |
|
给你一个字符串 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只包含小写英文字母和空格' '。- 相邻单词之间由单个空格隔开。
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 ansimport 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;
}
}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;
}
};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
}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