LeetCode.925-长按的名字(Long Pressed Name)

这是悦乐书的第355次更新,第380篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第217题(顺位题号是925)。你的朋友正在键盘上输入他的名字。 有时,在键入字符c时,键可能会被长按,键入的字符将被输入1次或更多次。

你检查键盘的键入字符。 如果可能是你的朋友姓名,则返回True,其中一些字符(可能没有)被长按。例如:

输入:name =“alex”,typed =“aaleex”
输出:true
说明:'alex'中的'a'和'e'被长按。

输入:name =“saeed”,typed =“ssaaedd”
输出:false
说明:'e'必须按两次,但它不在输入的输出中。

输入:name =“leelee”,typed =“lleeelee”
输出:true

输入:name =“laiden”,typed =“laiden”
输出:true
说明:没有必要长按任何字符。

注意

  • name.length <= 1000

  • typed.length <= 1000

  • name和typed的字符是小写字母。

02 第一种解法

题目的意思是typed中的某些字母会在name的基础上重复出现,当然,最理想的状态是nametyped完全相等。

想要结果返回true,需要满足以下条件:

  • 对应位置的字母要相等,typed中对应位置的字母出现次数只能等于或多于name中对应的字母。

  • name中有的字母以及出现次数,typed中必须有。

  • 在没处理完name中的字母时,typed不能已经处理完了。

反之,返回false就是上述三种情况的反例,只要出现一种就可以直接返回false

思路:遍历name中的字母,并统计当前字母出现的次数,直到遇到不同的字母,接着遍历typed中的字母,同样计数,然后判断前面我们分析的三种正常情况的反例,如果符合就直接返回false,三种反例都不符合,就将计数重置为1,相应的索引自加1。

此解法的时间复杂度为O(N),其中N代表字符串nametyped的长度之和,空间复杂度为O(1)

public boolean isLongPressedName(String name, String typed) {
    if (name.equals(typed)) {
        return true;
    }
    int count = 1, n = name.length();
    int j = 0, len = typed.length(), num = 1;
    for (int i=0; i<=n-1; i++) {
        while (i<n-1 && name.charAt(i) == name.charAt(i+1)) {
            count++;
            i++;
        }
        while (j<len-1 && typed.charAt(j) == typed.charAt(j+1)) {
            num++;
            j++;
        }
        if (j>len-1 || num < count || name.charAt(i) != typed.charAt(j) ) {
            return false;
        }
        count = 1;
        num = 1;
        j++;
    }
    return true;
}


03 第二种解法

我们也可以处理typed字符串,统计typed中和name相等的字母个数,如果最后和name的长度相等,就表明name中的字母全部都出现在了typed中。

此解法的时间复杂度为O(N),其中N代表字符串typed的长度,空间复杂度为O(1)

public boolean isLongPressedName2(String name, String typed) {
    if (name.equals(typed)) {
        return true;
    }
    int j = 0, n = name.length();
    int len = typed.length();
    for (int i=0; i<len; i++) {
        if (j<n && typed.charAt(i) == name.charAt(j)) {
            j++;
        }
    }
    return j == n;
}


04 小结

算法专题目前已连续日更超过六个月,算法题文章223+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 一、Python简介和环境搭建以及pip的安装 4课时实验课主要内容 【Python简介】: Python 是一个...
    _小老虎_阅读 5,837评论 0 10
  • 官网 中文版本 好的网站 Content-type: text/htmlBASH Section: User ...
    不排版阅读 4,481评论 0 5
  • 925.长按键入 题面 你的朋友正在使用键盘输入他的名字name。偶尔,在键入字符c时,按键可能会被长按,而字符可...
    狸奴丶阅读 532评论 0 0
  • HTML 5 HTML5概述 因特网上的信息是以网页的形式展示给用户的,因此网页是网络信息传递的载体。网页文件是用...
    阿啊阿吖丁阅读 4,092评论 0 0
  • Unicode®标准附录#9 UNICODE双向算法#### 摘要#### 本附件是一份关于字符定位的规范,主要描...
    Eriice阅读 4,920评论 0 6