LeetCode之Implement strStr()

本题是LeetCode28题,属于Easily级别

给出题目描述

Implement strStr().

Returns the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Update (2014-11-02): The signature of the function had been updated to return the index instead of the pointer. If you still see your function signature returns a char * or String, please click the reload button  to reset your code definition.

实质就是一个字符串首次匹配问题

相信大家肯定都知道BF(Brute-Force)以及KMP算法,这里就不再说多余的累赘的细节来阐述这两个算法,而是从另一个角度来感性的认识一下这两个算法

BF算法:

S:aaaachtr

P:aaac

这里可以发现前三位都是匹配的,但是最后一位不匹配,匹配的过程是S的i从0-3,P的j从0-3,失败了,很失望,最直观的想法就是我的S从下一个字符开始匹配

(多数保守派童鞋都是这么干的,很不幸,本人也是保守派)

S:aaaachtr

P:  aaac

但是社会总有一些激进青年,他们总能想出一条捷径,然后 他们就完成了变革,下面就让我们看一下KMP的激进思想

KMP算法:

核心思想就是当匹配不成功时,下一次匹配的位置能否只改变P的位置,而S不发生回溯(打破保守派)

最激进的童鞋提出了自己的方案(很不幸,本人从保守派转型时也是这么干的)

S:aaaachtr

P:aaac

当匹配不成功时,S位置i保持不变,P位置从j位置变为0

S:aaaachtr

P:       aaac

很明显,这位激进派的同学太有热情了,直接抛弃了以前匹配成功的(在他的潜意识中认为S匹配成功的 “aaa”已经没用了,可以扔掉了)

但是事实证明了,扔掉这一部分导致他改革失败了(力度过大了)

所以下次匹配的位置还需要仔细的斟酌一下,而不是如此的鲁莽

这样的位置才是我们想要的!!!!

S:aaaachtr

P:  aaac

P直接向后回溯了一个位置,回到了j=2的位置上,此时i=3,然后S[i]=P[j]='a',然后S[i+1]=P[j+1]='c',然后就没有然后了

因此的话,发现,要改革成功,必须要知道P中某一个位置当匹配不成功时,P往前回溯的下一个位置!

大家把改革的重点放在了P上,这里我们用一个next数组存放P中每一个位置匹配不成功时的下次回溯的位置

只看P:aaac(感性的认识一下)

P1:aaa

P2:  aac

大家发现这两个字符串怎么这么像,对(组合在一起就是aaac),P1[0,1]=P2[0,1],P1[2]!=P2[2],如果aac中的c匹配不成功,我能否把位置调整到aaa最后的位置看能够匹配

(万一要是S中就是aaa的话,那就太好了,这就和P1匹配上了),其实P1就是P中的一个子串,有一个优雅的名字叫做前缀,P2也有一个优雅的名字叫做后缀

因此如果能够找到这样的前缀和后缀,当后缀匹配不成功时,就转到前缀对应的位置去匹配(试试运气)

那现在的重点就是放在找前缀和后缀上

当P匹配到a时失败(一个字符有前缀和后缀吗,如果前后缀相同就是本身的话,岂不是死循环)

因此a的next[0]就是-1,一旦是是-1的话,就表示没有想要的子串(P和S必须同时向右移动重新从头匹配)

当P匹配到aa时失败(a和a分别是前缀和后缀)

如果后缀的a匹配不成功,那么前缀的a也肯定不成功,因此后缀a的next[1]就是前缀a的next[0],即next[1]=next[0]

(然后前缀a怎么的就不管了,因为前缀a已经有了next[0]了)

当P匹配到aaa时失败(前缀就是aa,后缀就是aa)

如果后缀的aa匹配不成功,那么前缀的aa肯定也匹配不成功,因此后缀aa中最后一个a的next就是前缀aa中最后一个a的next

即next[2]=next[1]

当P匹配到aaac时失败(前缀就是aaa,后缀就是aac)

如果后缀aac不匹配,那么前缀aaa是可能匹配的(WHY?????)

aac不匹配只因为c,如果正确的匹配字符就是a的话,那么就是aaa了,

那如果正确的字符还不是a呢,那就没什么好说的了,P的下次匹配的位置继续向前回溯

此时的j=next[j](位置j就变成了前缀aaa中最后一个字符a的next[j]了)

给出next=[-1,0,0,2]

有点绕晕了吧,多想想,肯定会感同身受的!!!

有了next,那么P和S匹配的时候是如此的easy了,为了加深大家的印象,在模拟一遍P和S的匹配过程

Step1:

S:aaaachtr

P:aaac

不匹配,哦,我们有了next,此时的i=3,j=3,next[j]=2

那么j=next[j]=2了,P向前回溯的位置就是j=2

Step2:

S:aaaachtr

P:  aaac

Step3:

S:aaaachtr

P:  aaac

没有然后了,匹配成功了。

KMP算法就到此结束了,按照这种思想是不是就能完成LeetCode上的字符串首次匹配了呢

贴出源代码(参考了网上关于KMP算法的一些代码)

class Solution {
public:
void getNext(char *p,int next[])
{
	int i=-1,j=0;
	int len=strlen(p);
	next[0]=-1;
	while(j<len-1) {

		if(i==-1 || p[i]==p[j]) {
			i++,j++;
			//下一个字符不匹配
			if(p[i]!=p[j])
				next[j]=i;
			else
				next[j]=next[i];
		}
		//当前字符不匹配,转到下一个匹配位置
		//和j位置看能否构成匹配
		else
			i=next[i];
	}
}

int strStr(char *haystack, char *needle) 
{
	if(haystack==NULL || needle==NULL)
		return -1;
	else if(needle[0]=='\0')
		return 0;
	//起始匹配的位置
	int len2=strlen(needle),len1=strlen(haystack);
	//len2长度大于len1
	if(len2>len1)
		return -1;
	int *next=new int[len2];
	//获得next
	getNext(needle,next);
	int i=0,j=0;
	//匹配
	while(i<len1 && j<len2) {

		if(j==-1 || haystack[i]==needle[j])
			i++,j++;
		else
			j=next[j];
	}
	delete []next;
	//子串全部匹配完
	if(j>=len2)
		return i-len2;
	return -1;
}
};

Accepted截图

发现这种方法是不是效率很高,有兴趣同学可以试试。

最后本人也是一直在做LeetCode,所有Problems的代码都开源了,并且都是Accepted过的

项目地址git@code.csdn.net:yiranyaoqiu/leetcode_problems.git

有兴趣同学可以参考其中另外的一些Problems。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏遊俠扎彪

《The C Puzzle Book》读书笔记

2008-10-10 赋值表达式的值是=右边的计算结果。如(x=3*2)=6. 实际编程中不要随便玩puzzle。 赋值操作符的优先级低于算术运算。如x=3+2...

20690
来自专栏HappenLee的技术杂谈

C++雾中风景9:emplace_back与可变长模板

emplace_back方法最大的改进就在与可以利用类本身的构造函数直接在内存之中构建对象,而不需要调用类的拷贝构造函数与移动构造函数。

8920
来自专栏猿人谷

[你必须知道的.NET] 第四回:后来居上:class和struct

本文将介绍以下内容: • 面向对象基本概念 • 类和结构体简介 • 引用类型和值类型区别 1. 引言 提起class和struct,我们首先的感觉是语法几乎相...

192100
来自专栏java一日一条

Java面试参考指南(一)

Java是一种基于面向对象概念的编程语言,使用高度抽象化来解决现实世界的问题。 面向对象的方法将现实世界中的对象进行概念化,以便于在应用之间进行重用。例如...

19330
来自专栏互扯程序

Java开发中遇到的那些坑!

之前在这个手册刚发布的时候看过一遍,当时感觉真是每个开发者都应该必读的一本手册,最近由于在总结一些我们日常开发中容易忽略的问题,可能是最低级的编码常见问题,往往...

7910
来自专栏PPV课数据科学社区

【学习】数据分析师的Python日记-第1天:谁来给我讲讲Python?

今天带来的是PYTHON,这是一篇非常有意思的文章。希望对大家有帮助。 ---- ---- 导语:或许是网上嘈嘈杂杂的关于大数据、互联网的新形势争论,或许是招聘...

21490
来自专栏AzMark

Python学习之面向对象

12230
来自专栏Albert陈凯

Scala Essentials: 字符串内插值

字符串插值 Scala是一门高度可扩展性的程序设计语言,保持微小的内核,但具有无穷大的扩展能力。例如,「字符串内插」功能,Scala语言并不是原生地支持该特性...

29470
来自专栏微信公众号:Java团长

Java开发中如何正确踩坑

之前在这个手册刚发布的时候看过一遍,当时感觉真是每个开发者都应该必读的一本手册,期间还写过一篇关于日志规约的文章:《下一个项目为什么要用 SLF4J》,最近由于...

11040
来自专栏企鹅号快讯

从零基础开始学习PHP(六)

发布上一篇博文的时候、不小心忘记添加打赏功能了、这篇文章补上!如文中有误之处、还望大神指出以便改正、也可以更好的帮助后来者学习。 ? PHP中变量的类型 目标 ...

20290

扫码关注云+社区

领取腾讯云代金券