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.

&nbsp;
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 was not in the typed output.


&nbsp;
Constraints:


	1 &lt;= name.length, typed.length &lt;= 1000
	name and typed consist of only lowercase English letters.


class Solution:
    def isLongPressedName(self, name: str, typed: str) -> bool:
        #dic for memoization
		dic = {}
        def dfs(i, j):
            if (i, j) in dic:
                return dic[(i, j)]
            
			#see if there is any case where both i and j reach to the end, cuz that will be the true condition
			#I only need one True 
            if i >= len(name):
                return j == len(typed)
			#we iterated through the end of typed, and not yet for name 
            if j >= len(typed):
                return False
            
			#if the characters don't match, return False
            if name[i] != typed[j]:
                dic[(i, j)] = False
                return False
            
			#if the two characters match
			#two options, either you move on (dfs(i + 1, j + 1)) or you consider it as an extra character (dfs(i, j + 1))
			#return if any of them is True, which means that i, j reach to the end as aforementioned
            dic[(i, j)] = dfs(i + 1, j + 1) or dfs(i, j + 1)
            return dic[(i, j)]
        
		#start from index 0, 0
        return dfs(0, 0)
class Solution {
    public boolean isLongPressedName(String name, String typed) {
        int i = 0;
        int j = 0;
        int m = name.length();
        int n = typed.length();

        while(j < n)
        {
            if(i < m && 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 == m;
    }
}
class Solution {
public:
    bool isLongPressedName(string name, string typed) {
        
        int j = 0, i = 0;
        for( ; i<name.length() && j<typed.length() ; i++)
        {
            if(name[i]!=typed[j++])
                return false;
            
            
            if(i<name.length() && name[i]!= name[i+1])
            {
                while(j<typed.length() && typed[j] == name[i])
                j++;
            }
        }
        
         return (i == name.length() && j == typed.length());
    }
};
var isLongPressedName = function(name, typed) {
    let i = 0;
    let j = 0;
    while (j < typed.length) {
        if (i < name.length && name[i] === typed[j]) i++;
        else if (typed[j] !== typed[j - 1]) return false; // this needs when name is traversed but there is tail of characters in typed
        j++; // Base case. keep going through typed anyway hitting first condition from time to time: (i < name.length && name[i] === typed[j])
    }

    return i === name.length;
};
Long Pressed Name