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

我不是女神ヾ 2022-01-07 11:59 160阅读 0赞

这是悦乐书的第**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`的基础上重复出现，当然，最理想的状态是`name`和`typed`完全相等。

想要结果返回`true`，需要满足以下条件：

*  对应位置的字母要相等，`typed`中对应位置的字母出现次数只能等于或多于`name`中对应的字母。
 *  `name`中有的字母以及出现次数，`typed`中必须有。
 *  在没处理完`name`中的字母时，`typed`不能已经处理完了。

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

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

此解法的时间复杂度为`O(N)`，其中`N`代表字符串`name`和`typed`的长度之和，空间复杂度为`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**\+篇，公众号对话框回复【**数据结构与算法**】、【**算法**】、【**数据结构**】中的任一关键词，获取系列文章合集。

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

转载于:https://www.cnblogs.com/xiaochuan94/p/11029752.html