小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进BAT互联网公司。可是努力了很久,别说BAT了,连TMD的橄榄枝都没有接到。
可是他越挫越勇。这不,今天他又去一家互联网小巨头公司面试了。
小史:只要先对比第一个字符和倒数第一个字符,再对比第二个字符和倒数第二个字符,以此类推。如果都相等,那就是回文串了。
题目:给你一个字符串,找出里面最长的回文子串。
例如,输入abcdcef,那么输出应该是cdc;
小史:可以遍历整个字符串,把每个字符和字符间的空隙当作回文的中心,然后向两边扩展来找到最长回文串。小史这次抢着分析时间和空间复杂度。
小史回到学校,把面试情况和吕老师说了一下。
吕老师:比如cabadabae用中心扩展的算法,我已经知道了第三位为中心的aba和第5位为中心的abadaba是回文,那么在判断第7位为中心的回文串的时候,有什么已知信息吗?
小史:已知第5位为中心的abadaba是回文,由回文的特性,就能够知道2-4位和6-8位对称,而又知道第3位为中心的aba是回文,所以2-4位是回文。这样的话,6-8位肯定是回文。
小史拿着笔在纸上画了半天,突然大叫一声。
小史:由于之前的计算,已经知道了第5位为中心的abadaba是回文,而第4位为中心的a的回文长度是1,所以第6位为中心的回文长度只能是1,不用再去扩展判断了。
小史:以第7位为中心的回文串的计算,由之前分析已经知道最小长度是3了,但是还是需要进行扩展,因为第9位是什么,根据之前的信息无法得知,需要扩展进行探索。
小史:而以第6位为中心的回文串的计算,并不需要进行探索了,因为根据之前第5位为回文中心串的信息、和第4位为回文中心串的信息,已经可以推断,第6位为回文中心串的长度只能为1。
1、首先,我们要记录下目前已知的回文串能够覆盖到的最右边的地方,就像案例中的第8位
2、同时,覆盖到最右边的回文串所对应的回文中心也要记录,就像案例中的第5位
3、以每一位为中心的回文串的长度也要记录,后面进行推断的时候能用到,就像案例中用到的以第3位为中心的回文和第4位为中心的回文
4、对于新的中心,我们判断它是否在右边界内,若在,就计算它相对右边界回文中心的对称位置,从而得到一些信息,同时,如果该中心需要进行扩展,则继续扩展就行。
小史:回文的中心有可能是两个字符中间,这种情况没有考虑到啊。
1、先对字符串进行预处理,两个字符之间加上特殊符号#;
2、然后遍历整个字符串,用一个数组来记录以该字符为中心的回文长度,为了方便计算右边界,我在数组中记录长度的一半(向下取整);
3、每一次遍历的时候,如果该字符在已知回文串最右边界的覆盖下,那么就计算其相对最右边界回文串中心对称的位置,得出已知回文串的长度;
4、判断该长度和右边界,如果达到了右边界,那么需要进行中心扩展探索。当然,如果第3步该字符没有在最右边界的“羽翼”下,则直接进行中心扩展探索。进行中心扩展探索的时候,同时又更新右边界;
5、最后得到最长回文之后,去掉其中的特殊符号即可。
理解了算法之后,小史的代码写起来也是非常快,不一会儿就写好了:
按相关度排序 按时间排序
按相关度排序 按回复数排序
全部 文档 代码类 工具类
手机号 正则的相关搜索
版权声明:文章内容来源于网络,版权归原作者所有,如有侵权请点击这里与我们联系,我们将及时删除。