题目地址:https://leetcode.com/contest/weekly-contest-107/problems/long-pressed-name/

题目描述

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.

Youexamine 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:

1、 name.length<=1000;
2、 typed.length<=1000;
3、 Thecharactersofnameandtypedarelowercaseletters.;

题目大意

打字输入名字的时候有可能手一滑把某些字符重复输入了,现在想知道输入的这个字符串是否可能由真正的名字打出来。

解题方法

周赛第一题,随时是个easy的题目,但是还是花了半个小时。

思想是,使用两个指针,分别指向名字和输入字符串,然后判断对应位置是否能够对应的上。具体做法是统计两个字符串中相同的字符串重复出现了多少次。我用一个变量指向name,每次向后移动,在每次开始的时候需要保存这个字符,然后我们需要找一下每个字符串后面有多少个相同的字符。最后需要判断,如果输入的这个字符的个数小于名字里面有的,那么就是输入错误了。当所有的判断都结束没有返回错误,那么就是成功了。

时间复杂度是O(N),空间复杂度是O(1).

class Solution(object):
    def isLongPressedName(self, name, typed):
        """
        :type name: str
        :type typed: str
        :rtype: bool
        """
        M = len(name)
        N = len(typed)
        i, j = 0, 0
        while i < M:
            c_i = name[i]
            count_i = 0
            count_j = 0
            while i < M and name[i] == c_i:
                i += 1
                count_i += 1
            while j < N and typed[j] == c_i:
                j += 1
                count_j += 1
            if count_j < count_i:
                return False
        return True

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

参考资料

DDKK.COM 弟弟快看-教程,程序员编程资料站,版权归原作者所有

本文经作者:负雪明烛 授权发布,任何组织或个人未经作者授权不得转发