关注Java领域相关技术 记录有趣的事情

LeetCode-925. 长按键入

US-B.Ralph
US-B.Ralph
2020-10-212020-10-22

问题地址

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
};
US-B.Ralph
LeetCode数据结构与算法算法

9 Comments

  • 头像
    free porn

    I reckon something genuinely interesting about your weblog so I bookmarked . Pearle Waverly Yolane

  • 头像
    BAYTOS6825

    Thank you!!1

  • 头像
    erotik

    Tout cela envahit le monde, comme une force de vie. Diena Haley Verlie

  • 头像
    bahis

    The information talked about within the article are a few of the ideal obtainable. Elva Jonathan Bess

  • 头像
    erotik

    I do not even know the way I stopped up right here, however I thought this publish was once good. Tarah Cecilius Skutchan

  • 头像
    bahis

    Hello to all, how is everything, I think every one is getting more from this web page, and your views are pleasant in support of new users. Opal Bay Hoover

  • 头像
    casino

    We are a gaggle of volunteers and opening a brand new scheme in our community. Camellia Reggy Luo

  • 头像
    sikis izle

    There is definately a great deal to know about this subject. I love all the points you have made. Larine Warner Anastasie

  • 头像
    joker

    Pretty! This has been an extremely wonderful post. Thank you for supplying this info. Eva Angelico Xena

Leave a Comment

邮箱地址不会被公开。 必填项已用*标注