描述
如果一个字符串恰好包含2个'h'、1个'i'和1个'o',我们就称这个字符串是hiho字符串。
如果一个字符串恰好包含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
题目:
https://hihocoder.com/problemset/problem/1485?sid=1507688
使用
尺取法
以第一个字母为起点一次寻找合适的坑点: 只包含字符串S的串
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner cin =new Scanner(System.in);
int ans=Solve(cin.nextLine());
System.out.print(ans);
}
static int min=Integer.MAX_VALUE;
private static int Solve(String s) {
int ans;
for (int i = 0; i < s.length(); i++) {
if(check(s,i)) {
ans = checkShort(s, i);
if (ans != -1) {//符合
if (ans < min) min = ans;
}
}
}
if (min==Integer.MAX_VALUE)
return -1;
else
return min;
}
private static int checkShort(String s, int i) {
int j=i;//1,2,3,4,5,
int H=0,I=0,O=0;//h两个
while (H<=2&&I<=1&&O<=1&&j<s.length()){
if(s.charAt(j)=='h') H++;
if(s.charAt(j)=='i') I++;
if(s.charAt(j)=='o') O++;
if(H==2&&I==1&&O==1){
return j-i+1;//hahaio
}
j++;
}
return -1;
}
private static boolean check(String s,int i) {
if(s.charAt(i)=='h'|s.charAt(i)=='i'|s.charAt(i)=='o'){
return true;
}
return false;
}
}
本文作者:Author: 寒光博客
文章标题:[hihoCoder]#1485 : hiho字符串
本文地址:https://dxoca.cn/Algorithm/10.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/Algorithm/10.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
很像朴素字符串匹配算法欸,有更好的算法吗
来测试一下评论~