leetcode 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
只包含小写英文字母和空格' '
。- 相邻单词之间由单个空格隔开。
题解——质因数分解法计算大数组合
数学思路
首先,每个单词都是独立的,假设第k个单词的排列为$num_k$,则答案就是
$$\prod_{k=1}^{n} num_k$$
而对于每一个$num_k$,就是求含有重复元素的全排列问题,根据高中数学排列组合的知识,有:
$$num_k=\frac{元素个数!}{\prod重复次数!}$$
例如,aaaabbc
的全排列就是
$$\frac{7!}{4!*2!}$$
代码实现
很自然地,我们只需要根据空格分词,对每一个单词统计字母重复次数,然后按照上面的公式计算即可,关键在于单词长度和重复次数都可能很大,要解决大数阶乘的计算问题。
首先要明确,(a/b)%c=(a%c)/(b%c)
是不成立的,除法取模并不像加减乘那样可以直接分离,而要通过逆元计算,不过我不会逆元😭😭😭。所以采用质因数分解法进行计算。
显然,$num_k$是一个正整数,这意味着$元素个数!$可以整除$\prod重复次数!$。那么,如果我们把分子分母同时进行质因数分解,可以想见,每一个质因数出现的次数,分子>=分母,所以可以对分母的所有质因数进行约分,剩下全是分子的了,接下来就可以用乘法根据(a*b)%c=(a%c)*(b%c)
计算了。
C++代码
1 | class Solution { |
本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 HeRen's Blog!
评论