LeetCode基础算法题第139篇:判断输入字符串是否是朋友的名字

技术提高是一个循序渐进的过程,所以我讲的leetcode算法题从最简单的level开始写的,然后> 到中级难度,最后到hard难度全部完。目前我选择C语言,Python和Java作为实现语言,因为这三种语言还是比较典型的。由于篇幅和> 精力有限,其他语言的实现有兴趣的朋友请自己尝试。初级难度说的差不多的时候,我打算再加点其他内容,我可能会从操作系统到协议栈,从分布式> 聊到大数据框架,从大数据聊到人工智能,… …。

如果有任何问题可以在文章后评论或者私信给我。

我会持续分享下去,敬请您的关注。

LeetCode 925. 输入的长按姓名(Long Pressed Name)

问题描述:

你的朋友打算在键盘上键入他的名字。有时候,当键入一个字符c的时候,按键可能被长按,导致字符c可能键入了多次。

你的任务是检查键入字符。 如果某些字符被长按了(也可能不存在任何字符被长按),那么这个输入可能是你朋友的名字,则返回true。

注:

  • name.length <= 1000;
  • typed.length <= 1000;
  • name 和 typed 都仅包含小写字母;

示例:

C语言实现:

第一种方法:

要满足返回true的条件与两个因素有关:

  1. 字符在name和typed中出现的顺序要保持一致;
  2. 对于每个字符在typed中每次连续出现的长度不能小于name中连续出现的长度;

例如name = “saeede”, typed = “ssaaeeddee”时。

name中字符出现的顺序是saede。typed中出现的顺序也是saede;且它们连续出现的个数,name是[1,1,2,1,1], typed是[2,2,2,2,2]。所以结果是true。

具体编码的时候,定义两个变量c1和c2,分别用来统计两个字符串同一字符连续出现的次数。同时遍历name和typed。

对于每个字符串,遇到不同字符的时候就暂停,比较不同的字符是否相等,如果相等再比较c2是否大于等于c1(c1和c2存放是前一个字符连续出现的次数)。如果字符不等或者,c2小于C1则返回false,继续直到遍历结束。

这个算法需要遍历两个字符串做统计,算法的复杂度是O(len(name)+len(typed))。

第二种方法:

如果typed可以返回true,那么除去typed中那些多键入的字符后,新的字符一定是和name相等的。

具体实现的方法依然是通过统计的方式。

我们定义一个变量c来做统计。遍历typed:

  1. 如果相应位置typed中的字符和name中的字符相等,那么c加1,接着比较typed和name的下一个字符;
  2. 否则,拿typed中的当前字符和typed的前一个字符再做比较,如果相等,说明这是一个多键入的字符,不做统计,typed移动到下一个字符,再和name中的那个字符做比较。

如此遍历下去,如果中间发生:typed的字符和name中的字符不等且typed的当前字符和typed的前一个字符也不等,应该返回false。

如果对typed的遍历成功结束,需要比较c和name的长度是否相等(考虑name是”dee”,typed是”dde”的情况)。

该方法仅仅对typed遍历,所以算法复杂度为O(len(typed))。

流程如下图所示:

我们使用第二种方法,代码如下:

在遍历前我们对一些情况做了先期处理,这样做可以使得在遍历循环中减少判断。

代码第7行,如果name的长度是0的时候,即为空字符串的时候,如果typed的也是0则返回true,如果typed的长度不是0,那么一定返回false。

代码第8行,如果typed的长度小于name,返回false。如果typed首字母和name的首字母不等,返回false,之所以将它单独拉出来,是为了代码第14行,不用做边界判断。

算法的时间开销不考虑其他因素仅仅从语言逻辑上考虑的话,主要取决于做了多少操作,操作越少耗时越小。因此算法中尽量减少遍历和循环操作就是为了减少操作。同样的,在遍历和循环中,做的事情越少,效率就会越高。所以对于一个判断,如果判断次数是常数次的,且能放到外面的,就绝不放到循环内部

Java语言实现:

Java 的实现和C语言的实现一致,不再撰述。代码如下:

Python语言实现:

Python 的实现和C语言的实现一致,不再撰述。代码如下:


谢谢大家一直以来的关注和支持!

我一直在努力的写好每一篇文章,画好每一份插图。但是作为一个996从业人员,时间精力十分有限。所以针对评论部分,以后只回答粉丝的问题和私信。希望仅仅是路过的朋友能够体谅,希望更多人关注《》,谢谢!


欢迎投稿本站:紫金网 » LeetCode基础算法题第139篇:判断输入字符串是否是朋友的名字