925. Long Pressed Name

Solution idea

Two Pointers - 两个数组双指针同向而行

• 这道题有很多坑

  • 看题意好像找到common subsequence就行，但实际上不是！！！
  • typed 里只能出现 name中出现的字母，并且相对顺序要与name中一致
    • Case 1: name=alex, typed=aaleelx 这种就不行因为l的顺序没有保持一致，第二个l出现在了 e 后头
    • Case 2: name=alex, typed=aaleexdd 这种也不行因为d没有在name中出现过 (虽然在最后也不行)

• 解法：

  • 两个数组双指针i, j同向而行
  • 双指针i, j指向的元素每一轮必须随时保持相同，直到双指针都走完了各自的数组
  • 如果当前轮i, j指向的元素相同，i, j同时右移直到指向不同元素；此时j右移跳过所有重复的元素直到指向不同元素；进入下一轮
  • 如果下一轮i, j指向了不相同元素，直接返回false (出现Case 1); 否则，重复上一步
  • 最后，如果 i, j没有全部走完各自的数组，返回false (出现Case 2)

Time complexity = $O(m+n)$

Resource

halfrost/LeetCode-Go

代码随想录-925.长按键入