LeetCode-925. 长按键入

问题地址

LeetCode每日一题/2020-10-21

LeetCode925. 长按键入

问题描述

规则

你的朋友正在使用键盘输入他的名字 name。偶尔，在键入字符 c 时，按键可能会被长按，而字符可能被输入 1 次或多次。

你将会检查键盘输入的字符 typed。如果它对应的可能是你的朋友的名字（其中一些字符可能被长按），那么就返回 True。

示例

• 示例1

输入：name = "alex", typed = "aaleex"
输出：true
解释：'alex' 中的 'a' 和 'e' 被长按。

• 示例2

输入：name = "saeed", typed = "ssaaedd"
输出：false
解释：'e' 一定需要被键入两次，但在 typed 的输出中不是这样。

• 示例3

输入：name = "leelee", typed = "lleeelee"
输出：true

• 示例4

输入：name = "laiden", typed = "laiden"
输出：true
解释：长按名字中的字符并不是必要的。

提示

• name.length <= 1000
• typed.length 0 , 则比较 typede[i] 是否与 typede[i-1] 相同；

解题思路

• 直接遍历字符串比较字符，需要考虑的条件较多，代码逻辑复杂。其实根据题意，我们可以定义两个指针，分别指向name、typed中当前字符
  • 我们扫描typed，如果 name[i]==typed[j] 说明typed中当前字符与name中当前字符相匹配，此时i、j分别加1；
  • 如果 name[i]！=typed[j] 我们需要检查typed当前字符是否是前一个字符的长按拖尾，即比较 typed[j]==typed[j-1] 如果相等则说明是存在长按拖尾j需要加1，否则返回false；
  • 最后当typed被扫描结束，如果 i==name.length， 则说明 name 被匹配

数据操作分析

• 见思路分析

复杂度分析

1. 时间复杂度
2. 空间复杂度

编码实现

• 遍历字符串比较字符

package fun.usb.algorithms;
import org.junit.Test;
public class LeetCode0925_LongPressedName {
    public boolean isLongPressedName(String name, String typed) {

        if (name == null || name == "" || typed == null || typed == "") return false;
        if (typed.length() < name.length()) return false;

        int len = name.length();
        int i = 0;
        char preChar = '0';
        while (len > 0) {
            if (i == 0 && name.equals(typed)) return true;
            if (i >= len) {
                for (int j = i; j < typed.length(); j++) {
                    if (typed.charAt(j - 1) != typed.charAt(j)) return false;
                }
                return true;
            }
            if (typed.charAt(i) != name.charAt(i)) {
                if (i <= 0) {
                    if (preChar != '0') {
                        if (preChar == typed.charAt(i)) {
                            typed = typed.substring(i + 1, typed.length());
                            continue;
                        }
                    }
                    return false;
                } else {
                    if (typed.charAt(i - 1) == typed.charAt(i)) {
                        name = name.substring(i, name.length());
                        typed = typed.substring(i + 1, typed.length());
                        if (typed.length() < name.length()) return false;
                        i = 0;
                        len = name.length();
                        continue;
                    }
                    return false;
                }
            }
            i++;
        }

        return true;
    }
}

• 双指针

package fun.usb.algorithms;
import org.junit.Test;
/**
 * 双指针
 */
public class LeetCode0925_LongPressedName1 {
    public boolean isLongPressedName(String name, String typed) {
        if (name == null || name == "" || typed == null || typed == "") return false;
        if (typed.length() < name.length()) return false;

        int i = 0, j = 0;
        while (j < typed.length()) {
            if (i < name.length() && name.charAt(i) == typed.charAt(j)) {
                i++;
                j++;
            } else if (j > 0 && typed.charAt(j) == typed.charAt(j - 1)) {
                j++;
            } else {
                return false;
            }
        }
        return i == name.length();
    }
}

官方解法

方法一 双指针

思路与算法：

• 根据题意能够分析得到：字符串 \textit{typed} 的每个字符，有且只有两种「用途」：
  • 作为 \textit{name} 的一部分。此时会「匹配」\textit{name} 中的一个字符
  • 作为长按键入的一部分。此时它应当与前一个字符相同。
• 如果 \textit{typed} 中存在一个字符，它两个条件均不满足，则应当直接返回 \textit{false}；否则，当 \textit{typed} 扫描完毕后，我们再检查 \textit{name} 的每个字符是否都被「匹配」了。

• 实现上，我们使用两个下标 i,j 追踪 \textit{name} 和 \textit{typed} 的位置。
  • 当 \textit{name}[i]=\textit{typed}[j] 时，说明两个字符串存在一对匹配的字符，此时将 i,j 都加 1。
  • 否则，如果 \textit{typed}[j]=\textit{typed}[j-1]，说明存在一次长按键入，此时只将 j 加 1。
• 最后，如果 i=\textit{name}.\textit{length}，说明 \textit{name} 的每个字符都被「匹配」了。

复杂度分析：

1. 时间复杂度:O(N+M)，其中 M,N 分别为两个字符串的长度。

2. 空间复杂度：O(1)。

编码实现

class Solution {
    public boolean isLongPressedName(String name, String typed) {
        int i = 0, j = 0;
        while (j < typed.length()) {
            if (i < name.length() && name.charAt(i) == typed.charAt(j)) {
                i++;
                j++;
            } else if (j > 0 && typed.charAt(j) == typed.charAt(j - 1)) {
                j++;
            } else {
                return false;
            }
        }
        return i == name.length();
    }
}

精彩评论

跳转地址1：925. 长按键入:【模拟匹配】详解

思路

这道题目一看以为是哈希，仔细一看不行，要有顺序。

所以模拟同时遍历两个数组，进行对比就可以了。

对比的时候需要一下几点：

name[i] 和 typed[j]相同，则i++，j++ （继续向后对比）
name[i] 和 typed[j]不相同
看是不是第一位就不相同了，也就是j如果等于0，那么直接返回false
不是第一位不相同，就让j跨越重复项，移动到重复项之后的位置，再次比较name[i] 和typed[j]
如果 name[i] 和 typed[j]相同，则i++，j++ （继续向后对比）
不相同，返回false
对比完之后有两种情况
name没有匹配完，例如name:”pyplrzzzzdsfa” type:”ppyypllr”
type没有匹配完，例如name:”alex” type:”alexxrrrrssda”

编码实现

class Solution {
public:
    bool isLongPressedName(string name, string typed) {
        int i = 0, j = 0;
        while (i < name.size() && j < typed.size()) {
            if (name[i] == typed[j]) { // 相同则同时向后匹配
                j++; i++;
            } else { // 不相同
                if (j == 0) return false; // 如果是第一位就不相同直接返回false
                while(typed[j] == typed[j - 1]) j++; // j跨越重复项，向后移动
                if (name[i] == typed[j]) { // j跨越重复项之后再次和name[i]匹配
                    j++; i++; // 相同则同时向后匹配
                }
                else return false;
            }
        }
        // 说明name没有匹配完，例如 name:"pyplrzzzzdsfa" type:"ppyypllr"
        if (i < name.size()) return false;

        // 说明type没有匹配完，例如 name:"alex" type:"alexxrrrrssda"
        while (j < typed.size()) {
            if (typed[j] == typed[j - 1]) j++;
            else return false;
        }
        return true;
    }
};

跳转地址1：「手画图解」双指针 | 925. 长按键入

思路

双指针，指针 i 和 j，循环体定为扫描typed。

如果字符相同，双指针都移动一位。

如果不一样，name[i – 1]存在，但typed[j] name[i – 1]，说明当前typed[j]是长按出来的，它右边可能也是长按出来的，指针 j 移动一位，指针 i 不动，继续考察。

如果不一样，且typed[j] != name[i – 1]或name[i – 1]就不存在，说明当前typed[j]键入错误，返回 false。

主旋律是扫描typed，指针 j 越界时，扫描结束，指针 i 理应也正好越界，返回 true。但有可能指针 i 没越界，即name还有字符未匹配，如下图：

编码实现

const isLongPressedName = (name, typed) => {
  let i = 0;
  for (let j = 0; j < typed.length; j++) {
    if (i < name.length && name[i] == typed[j]) { // i 和 j 都步进1
      i++;
    } else if (i - 1 >= 0 && typed[j] == name[i - 1]) { // i - 1 >= 0代表name[i - 1]存在
      // 当前typed[j]是长按出来的，它右边可能还有长按出来的，只是j++
    } else { // name[i - 1]不存在，或 typed[j] != name[i - 1]，键入错误，直接返回false
      return false;
    }
  }
  if (i > name.length - 1) { // 遍历结束，如果i越界了，说明i的字符也考察完了，返回true
    return true;
  }
  return false; // i 没越界，说明还有别的字符未匹配，返回false
};