[Two Pointers] LC 925. Long Pressed Name

Long Pressed Name - LeetCode

Goal

• Compare string A and B
• B might contain 1 or more of individual character from A
• Confirm if this condition applied

Highlight

• classic two pointers
• Iterate through the longer string, move the pointer on the shorter string only if certain condition was met

Strategy

• Two pointers, with the main pointer j , staying at the ‘typed’ string
• increment the index of the ‘name’ string by 1, only if name[i] == typed[j]
• use typed[j]==typed[j-1] to capture the repeated characters; because we incremented the i by 1 already
• When name[i]!=typed[j] and type[j]!=type[j-1] are False, return False

Complexity

• Time: O(N) → we traverse the longer string once
• Space: O(1) → no extra space was used

Code

class Solution:
    def isLongPressedName(self, name, typed):
        i = 0
        for j in range(len(typed)):
            if i < len(name) and name[i] == typed[j]:
                i += 1
            elif j == 0 or typed[j] != typed[j - 1]:
                return False
        return i == len(name)