0925._Long_Pressed_Name.md

925. Long Pressed Name

难度: Easy

刷题内容

原题连接

• https://leetcode.com/problems/long-pressed-name/description/

内容描述

Your friend is typing his name into a keyboard.  Sometimes, when typing a character c, the key might get long pressed, and the character will be typed 1 or more times.

You examine the typed characters of the keyboard.  Return True if it is possible that it was your friends name, with some characters (possibly none) being long pressed.

 

Example 1:

Input: name = "alex", typed = "aaleex"
Output: true
Explanation: 'a' and 'e' in 'alex' were long pressed.
Example 2:

Input: name = "saeed", typed = "ssaaedd"
Output: false
Explanation: 'e' must have been pressed twice, but it wasn't in the typed output.
Example 3:

Input: name = "leelee", typed = "lleeelee"
Output: true
Example 4:

Input: name = "laiden", typed = "laiden"
Output: true
Explanation: It's not necessary to long press any character.
 

Note:

name.length <= 1000
typed.length <= 1000
The characters of name and typed are lowercase letters.

解题方案

思路 1 - 时间复杂度: O(max(len(name),len(typed)))- 空间复杂度: O(1)******

两个字符串从index为0开始比较

• 如果该字符相同就同时往后挪, i += 1, j += 1
• 如果该字符不相同，那么
  • 如果typed的字符和name的前一个字符相等，那么j += 1
  • 如果typed的字符和name的前一个字符不相等，肯定不行，直接返回False
• while循环完了，如果 i < len(name)，那么说明name没有被比较晚，肯定不行，直接返回False
• 如果typed还没有完，即j < len(typed)，那么如果typed剩下的所有字符不是都与name的最后一个字符相等的话，就说明不行，直接返回False，否则返回True

class Solution(object):
    def isLongPressedName(self, name, typed):
        """
        :type name: str
        :type typed: str
        :rtype: bool
        """
        i, j = 0, 0
        prev = None
        
        while i < len(name) and j < len(typed):
            if name[i] == typed[j]:
                prev = name[i]
                i += 1
                j += 1
            else:
                if typed[j] == prev:
                    j += 1
                else:
                    return False
        if i < len(name):
            return False
        
        while j < len(typed):
            if typed[j] != prev:
                return False
            else:
                j += 1
                
        return True