ZYF005 完美字符串
大约 1 分钟
ZYF005 完美字符串
【算法】 双指针、滑动窗口
【C++】 双指针、字符串、cnt数组
【难度】 普及/提高−
一、题目简述
个单词(全小写),找一段连续单词,使得这些单词包含全部 26 个小写字母。求满足条件的最短段的字母总数(不是单词数)。
二、解题思路
和逛画展类似,但这里是找包含所有 26 个字母的最短单词段。
- 滑动窗口遍历单词
- 对每个单词,统计其中的字母
- 维护窗口内各字母的出现次数
- 当包含全部 26 个字母时,尝试收缩
- 用
preLen前缀和快速计算窗口内字母总数
注意:题目要求输出的是满足条件的最短段的字母总数(所有单词字母数之和),而非单词个数。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
string words[N];
int preLen[N]; // 单词长度前缀和
int letterCnt[26]; // 当前窗口各字母出现次数
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> words[i];
preLen[i] = preLen[i - 1] + words[i].length();
}
int l = 1, total = 0; // total = 当前有几种字母
int ans = 2e9;
for (int r = 1; r <= n; r++) {
// 加入单词 r 的字母
for (char c : words[r]) {
int idx = c - 'a';
if (letterCnt[idx] == 0) total++;
letterCnt[idx]++;
}
while (total == 26) {
int curLen = preLen[r] - preLen[l - 1];
ans = min(ans, curLen);
// 尝试移除单词 l
for (char c : words[l]) {
int idx = c - 'a';
letterCnt[idx]--;
if (letterCnt[idx] == 0) total--;
}
l++;
}
}
cout << ans << endl;
return 0;
}四、复杂度分析
- 时间复杂度:。每个单词的每个字母进出窗口各一次。
- 空间复杂度:,用于存储单词和前缀和数组。
