028 Implement strStr() 实现 strStr()
2024-09-08 19:51:21
实现 strStr()。
返回蕴含在 haystack 中的 needle 的第一个字符的索引，如果 needle 不是 haystack 的一部分则返回 -1 。
例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
详见：https://leetcode.com/problems/implement-strstr/description/
Java实现：
方法一：暴力解
class Solution {
public int strStr(String haystack, String needle) {
int hsize=haystack.length();
int nsize=needle.length();
int i=0;
int j=0;
while(i<hsize&&j<nsize){
if(haystack.charAt(i)==needle.charAt(j)){
++i;
++j;
}else{
i=i-j+1;
j=0;
}
}
if(j==nsize){
return i-j;
}else{
return -1;
}
}
}
方法二：KMP算法
class Solution {
public int strStr(String s, String p) {
int i=0;
int j=-1;
int ps=p.length();
int[] next=new int[ps+1];
next[0]=-1;
while(i<ps){
if(j==-1||p.charAt(i)==p.charAt(j)){
++i;
++j;
next[i]=j;
}else{
j=next[j];
}
}
int ss=s.length();
i=0;
j=0;
while(i<ss&&j<ps){
if(j==-1||s.charAt(i)==p.charAt(j)){
++i;
++j;
}else{
j=next[j];
}
}
if(j==ps){
return i-j;
}
return -1;
}
}
最新文章
- win64位安装python-mysqldb1.2.5
- odi 12.2.1.1新特性
- miniUI datagrid 获取序号
- DDD：使用EntityFramework的话，如果只为聚合根设计仓储，其它实体如何处理？
- Linux中MySQL5.5解压版普通用户安装
- Linux SO_KEEPALIVE属性,心跳
- WordPress Think Responsive Themes ‘upload_settings_image.php’任意文件上传漏洞
- cocos2dx 文件处理
- cocos2d-x3.2中加入Android手机震动
- OBIEE 简介
- HDU 4044 GeoDefense
- java删除数组中的第ｎ个数
- 【learning】多项式相关（求逆、开根、除法、取模）
- Vue.js 学习笔记 第1章 初识Vue.js
- C++中几种输入输出cin、cin.getline()、getline()、sscanf()、sprintf()、gets()等
- C++系列总结——volatile关键字
- ansible笔记（4）：常用模块之文件操作
- rails gem更换ruby-china源
- enum 关键字
- memcached（一）：linux下memcached安装以及启动