#1485 : hiho字符串
时间限制:10000ms
单点时限:1000ms
内存限制:256MB
描述
如果一个字符串恰好包含2个'h'、1个'i'和1个'o'，我们就称这个字符串是hiho字符串。
例如"oihateher"、"hugeinputhugeoutput"都是hiho字符串。
现在给定一个只包含小写字母的字符串S，小Hi想知道S的所有子串中，最短的hiho字符串是哪个。
输入
字符串S
对于80%的数据，S的长度不超过1000
对于100%的数据，S的长度不超过100000
输出
找到S的所有子串中，最短的hiho字符串是哪个，输出该子串的长度。如果S的子串中没有hiho字符串，输出-1。
- 样例输入
-
happyhahaiohell
样例输出 -
5
思路：
在给定的字符串S中找到最小的窗口使其完全包含hiho。不能多也不能少，
时间复杂度：O(l1+4)（l1为字符串S的长度）
空间复杂度：O(4)
AC代码：
#include "iostream"#include "string"#include "string.h"#include "vector"#include "map"#include "algorithm"using namespace std;char c[256];int ans = 100005;int main(){ string s; while (cin >> s) { memset(c, 0, sizeof(c)); int l = s.length(); for (int i = 0,j=0; i < l; i++) { while (j < l && (c['h'] < 2 || c['i'] < 1 || c['o'] < 1)) { c[s[j]]++; j++; if (c['h'] > 2 || c['i'] > 1 || c['o'] > 1) break; } if (c['h'] == 2 && c['i'] == 1 && c['o'] == 1) { ans = min(ans, j - i); } c[s[i]]--; } if (ans == 100005) ans = -1; cout << ans << endl; }}
附上LeetCode上一题类似的滑动窗口问题
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).
For example,
S ="ADOBECODEBANC"T = "ABC" Minimum window is "BANC".
代码：
1 #include "iostream" 2 #include "string" 3 #include "string.h" 4 using namespace std; 5 6 string str; 7 int ans = 100005; 8 9 int count1[256];10 int count2[256];11 12 string minWindow(string S, string T) {13 if (T.size() == 0 || S.size() == 0)14 return "";15 16 memset(count1, 0, sizeof(count1));17 memset(count2, 0, sizeof(count2));18 19 for (int i = 0; i < T.size(); i++)20 {21 count1[T[i]]++;22 count2[T[i]]++;23 }24 25 int count = T.size();26 27 int start = 0;28 int minSize = 100005;29 int minStart;30 for (int end = 0; end < S.size(); end++)31 {32 if (count2[S[end]] > 0)33 {34 count1[S[end]]--;35 if (count1[S[end]] >= 0)36 count--;37 }38 if (count == 0)39 {40 while (true)41 {42 if (count2[S[start]] > 0)43 {44 if (count1[S[start]] < 0)45 count1[S[start]]++;46 else47 break;48 }49 start++;50 }51 52 if (minSize > end - start + 1)53 {54 minSize = end - start + 1;55 minStart = start;56 }57 }58 }59 60 if (minSize == ans)61 return "";62 63 string ret(S, minStart, minSize);//string 构造函数64 return ret;65 }66 67 int main()68 {69 while (cin >> str)70 {71 int l = minWindow(str, "hiho").length();72 if (l<4)73 cout << -1 << endl;74 else75 cout << l << endl;76 }77 }