925. Long Pressed Name.md

925. Long Pressed Name

---

leetcode-cn Daily Challenge on October 21th, 2020.

---

Difficulty : Easy

Related Topics : Two Pointers、String

---

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.

Constraints:

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

---

Solution

• mine
  • Java

    • Two Pointer Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.4 MB, less than 8.33% of Java online submissions

      // O(T)time 
      // O(1)space
      // T = typed.length();
      public boolean isLongPressedName(String name, String typed) {
          int len1 = name.length();
          int len2 = typed.length();
          if (len2 < len1) {
              return false;
          }
          int i = 0, j = 0;
          while (i <= len1 && j < len2){
              if(i < len1 && name.charAt(i) == typed.charAt(j)){
                  i++;
                  j++;
              }else if (i > 0 && name.charAt(i - 1) == typed.charAt(j)){
                  j++;
              }else {
                  break;
              }
          }
          return i == len1 && j ==len2;
      }
      

    • LinkedList Runtime: 1 ms, faster than 50.93%, Memory Usage: 37.4 MB, less than 8.33% of Java online submissions

      // O(T)time 
      // O(N)space
      // N = name.length()  T = typed.length();
      public boolean isLongPressedName(String name, String typed) {
          int len1 = name.length();
          int len2 = typed.length();
          if (len2 < len1) {
              return false;
          }
          LinkedList<Character> t = new LinkedList<>();
          for (int i = 0; i < len1; i++) {
              t.add(name.charAt(i));
          }
          Character removed = 0;
          int i = len2 - 1;
          for (; i >= 0; i--) {
              if (!t.isEmpty() && typed.charAt(i) == t.getLast()) {
                  removed = t.removeLast();
              } else if (removed != typed.charAt(i)) {
                  break;
              }
          }
          return t.isEmpty() && i == -1;
      }
      

---

• the most votes

Two Pointer Runtime: 0 ms, faster than 100.00%, Memory Usage: 37.6 MB, less than 8.33% of Java online submissions

// O(T)time 
// O(1)space
// T = typed.length();
public boolean isLongPressedName(String name, String typed) {
    int i = 0, m = name.length(), n = typed.length();
    for (int j = 0; j < n; ++j)
        if (i < m && name.charAt(i) == typed.charAt(j))
            ++i;
        else if (j == 0 || typed.charAt(j) != typed.charAt(j - 1))
            return false;
    return i == m;
}

---

• the leetcode's solution

• Group into Blocks Runtime: 1 ms, faster than 50.93%, Memory Usage: 37.5 MB, less than 8.33% of Java online submissions

  class Solution {
      public boolean isLongPressedName(String name, String typed) {
          Group g1 = groupify(name);
          Group g2 = groupify(typed);
          if (!g1.key.equals(g2.key))
              return false;
  
          for (int i = 0; i < g1.count.size(); ++i)
              if (g1.count.get(i) > g2.count.get(i))
                  return false;
          return true;
      }
  
      public Group groupify(String S) {
          StringBuilder key = new StringBuilder();
          List<Integer> count = new ArrayList();
          int anchor = 0;
          int N = S.length();
          for (int i = 0; i < N; ++i) {
              if (i == N-1 || S.charAt(i) != S.charAt(i+1)) { // end of group
                  key.append(S.charAt(i));
                  count.add(i - anchor + 1);
                  anchor = i+1;
              }
          }
  
          return new Group(key.toString(), count);
      }
  }
  
  class Group {
      String key;
      List<Integer> count;
      Group(String k, List<Integer> c) {
          key = k;
          count = c;
      }
  }
  

---