返回介绍

solution / 2500-2599 / 2514.Count Anagrams / README_EN

发布于 2024-06-17 01:03:04 字数 4775 浏览 0 评论 0 收藏 0

2514. Count Anagrams

中文文档

Description

You are given a string s containing one or more words. Every consecutive pair of words is separated by a single space ' '.

A string t is an anagram of string s if the ith word of t is a permutation of the ith word of s.

  • For example, "acb dfe" is an anagram of "abc def", but "def cab" and "adc bef" are not.

Return _the number of distinct anagrams of _s. Since the answer may be very large, return it modulo 109 + 7.

 

Example 1:

Input: s = "too hot"
Output: 18
Explanation: Some of the anagrams of the given string are "too hot", "oot hot", "oto toh", "too toh", and "too oht".

Example 2:

Input: s = "aa"
Output: 1
Explanation: There is only one anagram possible for the given string.

 

Constraints:

  • 1 <= s.length <= 105
  • s consists of lowercase English letters and spaces ' '.
  • There is single space between consecutive words.

Solutions

Solution 1

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
}

Solution 2

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

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文