代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给你一个字符串 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
只包含小写英文字母和空格 ' '
。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
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;
}
}
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
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。