【算法】字符串就是这么简单

作者: | 更新日期:

数据结构中的基础知识有很多,计划一点点介绍,这篇文章介绍字符串。

本文首发于公众号:天空的代码世界,微信号:tiankonguse
原文地址:https://mp.weixin.qq.com/s/T2SoYIOOTT279DIWfxlyIA

一、背景

这篇文章简单的介绍一下字符串的使用,然后来看几道对应的例子。
注:每次我都会把对应的练习题地址发送到群里,建议想学算法的朋友耐心的做一下这些题。

二、字符串简介

字符串其实就是一个字符元素组成的数组。
它几乎拥有数组的所有操作功能。

当然,字符串和数组也有一些区别。
这里主要介绍使用字符串时需要注意的问题,尤其是不同语言之间的差异。

1.比较函数

字符串一般有自己的比较函数,但是不一定是==运算符。
C++里面,我们可以使用这个运算符,但是在Java里面,我们就不能使用这个运算符了。
Java里面,==用于判断两个对象是否是同一个对象,但是不同对象的值可能是相同的。

2.可变性

不可变意味着字符串初始化后,就不能在修改它的内容了。
当然,在C++中,默认字符串是可变的,我们可以像数组那样来修改字符串的内容。
而在Java中,每个字符串都是一个不可变的对象,当对字符串操作时,都会生成新的字符串(很消耗性能)。

3.附加操作

由于字符串已经作为编程语言的内置类型了,所以增加了一些额外的常见操作函数。
比如字符串拼接、查找、子串截取等。

三、二进制求和

在《数组就是这么简单》里面有一道题,叫做加一
很多人说这道题太简单了,现在就加大点难度,两个字符串组成的二进制数字相加求和。

其实,对于大整数运算,有一个标准的步骤。

第一步将字符串翻转。
平常我们纸上手动计算大数相加时,都是低位对齐,然后从低位到高位计算。
而计算机里的数字,低位在后面,高位在前面,所以需要字符串翻转。

第二步是求出答案可能的最大长度,然后在两个字符串上高位补零。
由于可能进位,所以一般是两个字符串的最大长度再加一,这样可以保证计算时不用考虑特殊边界情况。

第三步就循环相加,需要进位则进位,直到循环结束。

第四步需要删除答案高位多于的0。
由于答案可能也是0,所以答案要保留一位。

第五步是对答案翻转,使得答案满足计算机的要求:高位在前面低位在后面。

通过这样五步,所有的大整数运算都可以解决了。

四、实现strStr

首先我们需要明白strStr函数的含义。
根据文档定义,这个函数的功能是查找字符串子串的第一个位置。
如果不存在子串,则返回-1

对于这道题,最简单的就是暴力解决。
具体来说就是枚举第一个字符串的每一个位置来当做起点,然后循环判断是否和第二个字符串匹配。
当然,这个复杂度是O(n * m)的。

面对上面的暴力方法,其实我们有一个更快的方法,名字叫做KMP
这个算法使用语言描述的方式来理解的话很简单,但是实现后看代码理解起来比较难。

先来看语言描述层面的意思。

假设我们从某个位置P开始和字符串needle比较,比较了10个字符后发现不同了。
在暴力方法中,我们直接从P+1位置重新开始从头比较。

其实,我们从P ~ P+10的字符我们都已经扫描过了,而且P ~ P+9的字符都和needle的前缀相同。
既然扫描过了,我们能不能直接来判断下个位置应该从哪个位置开始比较呢?

比如P ~ P+9 的子串对应于1234512345
如果我们直接从下个位置开始比较,则P+1位置的值时2,而needle第一个位置的值时1,显然不成立。
同理,P+2位置值是3也不成立。
直到P+5位置值是1是才成立,而且也可以判断出P+5 ~ P+9都是成立的,我们只需要判断P+10的位置是不是1
KMP做到就是这个工作。

这个算法会先对needle进行预处理,计算出到某个位置不相等时,下一次要从哪里开始。
然后我们扫描目标字符串时,只需要不断的对比,发现不相等了,快速的移动到下一个合适的位置继续比较。
由于这里没有进行冗余比较,复杂度是O(N + M),其中NM分别是两个字符串的长度。

语言描述的含义说完了,剩下的就是使用代码将我们描述的逻辑实现了。
这个实现还是相当抽象的,所以大家看着代码,找个例子模拟一下才能理解。

五、最长公共前缀

题意:给N个字符串,求最长公共前缀。

这道题没啥说的,循环比较即可。

六、最后

对于字符串,相关题型其实特别多。
KMP是首先遇到的最优技术含量的一个算法,这里关键是理解预处理的next数组的含义,后面会有各种变种的题型的。

-EOF-

本文首发于公众号:天空的代码世界,微信号:tiankonguse
原文地址:https://mp.weixin.qq.com/s/T2SoYIOOTT279DIWfxlyIA

点击查看评论

关注公众号,接收最新消息

关注小密圈,学习各种算法

tiankonguse +
穿越