本文涉及的基础知识点
C++算法:前缀和、前缀乘积、前缀异或的原理、源码及测试用例 包括课程视频
LeetCode2949统计美丽子字符串
给你一个字符串 s 和一个正整数 k 。
用 vowels 和 consonants 分别表示字符串中元音字母和辅音字母的数量。
如果某个字符串满足以下条件,则称其为 美丽字符串 :
vowels == consonants,即元音字母和辅音字母的数量相等。
(vowels * consonants) % k == 0,即元音字母和辅音字母的数量的乘积能被 k 整除。
返回字符串 s 中 非空美丽子字符串 的数量。
子字符串是字符串中的一个连续字符序列。
英语中的 元音字母 为 ‘a’、‘e’、‘i’、‘o’ 和 ‘u’ 。
英语中的 辅音字母 为除了元音字母之外的所有字母。
示例 1:
输入:s = “baeyh”, k = 2
输出:2
解释:字符串 s 中有 2 个美丽子字符串。
- 子字符串 “baeyh”,vowels = 2([“a”,“e”]),consonants = 2([“y”,“h”])。
可以看出字符串 “aeyh” 是美丽字符串,因为 vowels == consonants 且 vowels * consonants % k == 0 。 - 子字符串 “baeyh”,vowels = 2([“a”,“e”]),consonants = 2([“b”,“y”])。
可以看出字符串 “baey” 是美丽字符串,因为 vowels == consonants 且 vowels * consonants % k == 0 。
可以证明字符串 s 中只有 2 个美丽子字符串。
示例 2:
输入:s = “abba”, k = 1
输出:3
解释:字符串 s 中有 3 个美丽子字符串。 - 子字符串 “abba”,vowels = 1([“a”]),consonants = 1([“b”])。
- 子字符串 “abba”,vowels = 1([“a”]),consonants = 1([“b”])。
- 子字符串 “abba”,vowels = 2([“a”,“a”]),consonants = 2([“b”,“b”])。
可以证明字符串 s 中只有 3 个美丽子字符串。
示例 3:
输入:s = “bcdf”, k = 1
输出:0
解释:字符串 s 中没有美丽子字符串。
参数范围:
1 <= s.length <= 5 * 104
1 <= k <= 1000
s 仅由小写英文字母组成。
方法一
分析
时间复杂度
O(nn)
大致步骤
记录前缀和后,枚举左右端点。
setVowel | 所有元音字符 |
vPre1[i] | 前i个字符中元音的数量 |
vPre2[i] | 前i个字符中辅音的数量 |
代码
核心代码
class Solution {
public:
int beautifulSubstrings(string s, int k) {
m_c = s.length();
std::unordered_set setVowel = { ‘a’,‘e’,‘i’,‘o’ , ‘u’ };
vector vPre1 = { 0 }, vPre2 = { 0 };
for (const char& ch : s)
{
if (setVowel.count(ch))
{
vPre1.emplace_back(vPre1.back() + 1);
vPre2.emplace_back(vPre2.back() );
}
else
{
vPre1.emplace_back(vPre1.back() );
vPre2.emplace_back(vPre2.back() + 1);
}
}
int iRet = 0;
for(int i = 0 ; i < m_c ; i++ )
for (int j = i; j < m_c; j++)
{
const int iNum1 = vPre1[j + 1] - vPre1[i];
const int iNum2 = vPre2[j + 1] - vPre2[i];
if (iNum1 != iNum2)
{
continue;
}
if (0 != iNum1 * iNum2% k )
{
continue;
}
iRet++;
}
return iRet;
}
int m_c;
};
测试用例
template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}
template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}
int main()
{
string s;
int k,res;
{
Solution slu;
s = “baeyh”;
k = 2;
res = slu.beautifulSubstrings(s, k);
Assert(res, 2);
}
{
Solution slu;
s = “abba”;
k = 1;
res = slu.beautifulSubstrings(s, k);
Assert(res, 3);
}
{
Solution slu;
s = “bcdf”;
k = 1;
res = slu.beautifulSubstrings(s, k);
Assert(res, 0);
}
{
Solution slu;
s = “ihroyeeb”;
k = 5;
res = slu.beautifulSubstrings(s, k);
Assert(res, 0);
}
}
方案二
s[left,right]是美丽字符的条件。
一,元音辅音相等。我们记录所有sub[left] = vPre1[left]-vPre2[left],即元音辅音之差。如果sub[left]等于sub[right],则元音辅音相等。
二,数量的平方是k的倍数。我可以转成等效问题:数量必须是m的倍数。如:k=4,则m=2。k=3,则m=3。k=12,m=6。显然:m小于等于k,且m不会为0。对于每个left,我们无需记录它的元音数量,只需要记录它的元音数量%m。
原理:
s[0…i-1]有n1个元音,s[i,j]有n2个元音,n3 = n2- n1 ,如何判断n3n3%k=0。
显然: (n3%k)(n3%k)%k ⟺ \iff ⟺ n3n3%k
n3,n2,n1都对k求余。
由于n3 < k。所有n3n3 < k × \times × k,要想%k等于0,只能 是0, k ,2k ,3k ⋯ \cdots ⋯ ,最多k种。时间复杂度降到 O(nk)。
许多n3是非法,我用程序跑了一下,1000以内最多31个合法n3。O(31n)可以通过了。可以继续优化到O(1)。
除0外,n3n3 %k 等同余n3n3 = bk (a>0)
k可以表示为: a1n1a2n2a3n3 ⋯ \cdots ⋯amnm
n3 至少为 a1(n1+1)/2 a2(n2+1)/2 ⋯ \cdots ⋯ m2(nm+1)/2,也就是上文的m。
n3n3是k的倍数,则n3必定m的倍数。n3为0,也符合。故 n3 % m ==0一定符合。
不等于0 一定不符合。
一, n 3 m o d m ≠ 0 → n 3 ≠ 0 n3 \mod m \neq 0 \rightarrow n3 \neq 0 n3modm=0→n3=0
二,令n3 = e*m+c ,由于c ∈ \in ∈[0,m) 所以c3 一定不是m的倍数。
时间复杂度
如果用有序映射记录状态的数量,则时间复杂度为:O(nlognm)。
枚举每个每个美丽字符串的右端点时间复杂度O(n),查询合法的对应left数量O(lognm)。如果用哈希映射记录状态和数量,总时间复杂度降到O(n)。
代码
class Solution {
public:
int beautifulSubstrings(string s, int k) {
m_c = s.length();
std::unordered_set<char> setVowel = { 'a','e','i','o' , 'u' };
vector<int> vPre1 = { 0 }, vPre2 = { 0 };
for (const char& ch : s)
{
if (setVowel.count(ch))
{
vPre1.emplace_back(vPre1.back() + 1);
vPre2.emplace_back(vPre2.back());
}
else
{
vPre1.emplace_back(vPre1.back());
vPre2.emplace_back(vPre2.back() + 1);
}
}
int m = 0;
for (m = 1; 0 != m * m % k; m++);
int iRet = 0;
std::unordered_map<int, std::unordered_map<int,int>> mSub;
for (int i = 0; i < m_c; i++)
{
const int iSub = vPre1[i+1] - vPre2[i+1];
const int iNeed = vPre1[i + 1] % m;
if (mSub.count(iSub))
{
if(mSub[iSub].count(iNeed))
{
iRet += mSub[iSub][iNeed];
}
}
{
const int iSub = vPre1[i] - vPre2[i];
mSub[iSub][vPre1[i]%m]++;
}
}
return iRet;
}
int m_c;
};
优化代码
分析
优化点:
一,无需前缀和,记录当前元音数量就可以了。当前辅音数量=当前字符总数量-当前元音数量。
二,用std::pair<int,int> 做key。
代码
class Solution {
public:
int beautifulSubstrings(string s, int k) {
m_c = s.length();
std::unordered_set<char> setVowel = { 'a','e','i','o' , 'u' };
int m = 0;
for (m = 1; 0 != m * m % k; m++);
int iRet = 0;
int iVowelNum = 0;
std::map<std::pair<int, int>, int> mSubVowelToNum;
for (int i = 0; i < m_c; i++)
{
const int preVowel = iVowelNum;
if (setVowel.count(s[i]))
{
iVowelNum++;
}
const int iSub = iVowelNum - (i+1- iVowelNum);//当前元音数量减辅音数量
auto pr = std::make_pair(iSub, iVowelNum%m);
if (mSubVowelToNum.count(pr))
{
iRet += mSubVowelToNum[pr];
}
{
const int iSub = preVowel - (i - preVowel);
auto pr = std::make_pair(iSub, preVowel%m);
mSubVowelToNum[pr]++;
}
}
return iRet;
}
int m_c;
};