這是悅樂書的第355次更新，第380篇原創(chuàng)
01 看題和準備
今天介紹的是LeetCode算法題中Easy級別的第217題（順位題號是925）。你的朋友正在鍵盤上輸入他的名字。 有時，在鍵入字符c時，鍵可能會被長按，鍵入的字符將被輸入1次或更多次。
你檢查鍵盤的鍵入字符。 如果可能是你的朋友姓名，則返回True，其中一些字符（可能沒有）被長按。例如：
輸入：name =“alex”，typed =“aaleex”
輸出：true
說明：'alex'中的'a'和'e'被長按。
輸入：name =“saeed”，typed =“ssaaedd”
輸出：false
說明：'e'必須按兩次，但它不在輸入的輸出中。
輸入：name =“l(fā)eelee”，typed =“l(fā)leeelee”
輸出：true
輸入：name =“l(fā)aiden”，typed =“l(fā)aiden”
輸出：true
說明：沒有必要長按任何字符。
注意：
name.length <= 1000
typed.length <= 1000
name和typed的字符是小寫字母。
02 第一種解法
題目的意思是typed中的某些字母會在name的基礎上重復出現(xiàn)，當然，最理想的狀態(tài)是name和typed完全相等。
想要結果返回true，需要滿足以下條件：
對應位置的字母要相等，
typed中對應位置的字母出現(xiàn)次數(shù)只能等于或多于name中對應的字母。name中有的字母以及出現(xiàn)次數(shù)，typed中必須有。在沒處理完
name中的字母時，typed不能已經處理完了。
反之，返回false就是上述三種情況的反例，只要出現(xiàn)一種就可以直接返回false。
思路：遍歷name中的字母，并統(tǒng)計當前字母出現(xiàn)的次數(shù)，直到遇到不同的字母，接著遍歷typed中的字母，同樣計數(shù)，然后判斷前面我們分析的三種正常情況的反例，如果符合就直接返回false，三種反例都不符合，就將計數(shù)重置為1，相應的索引自加1。
此解法的時間復雜度為O(N)，其中N代表字符串name和typed的長度之和，空間復雜度為O(1)。
public boolean isLongPressedName(String name, String typed) {
if (name.equals(typed)) {
return true;
}
int count = 1, n = name.length();
int j = 0, len = typed.length(), num = 1;
for (int i=0; i<=n-1; i++) {
while (i<n-1 && name.charAt(i) == name.charAt(i+1)) {
count++;
i++;
}
while (j<len-1 && typed.charAt(j) == typed.charAt(j+1)) {
num++;
j++;
}
if (j>len-1 || num < count || name.charAt(i) != typed.charAt(j) ) {
return false;
}
count = 1;
num = 1;
j++;
}
return true;
}
03 第二種解法
我們也可以處理typed字符串，統(tǒng)計typed中和name相等的字母個數(shù)，如果最后和name的長度相等，就表明name中的字母全部都出現(xiàn)在了typed中。
此解法的時間復雜度為O(N)，其中N代表字符串typed的長度，空間復雜度為O(1)。
public boolean isLongPressedName2(String name, String typed) {
if (name.equals(typed)) {
return true;
}
int j = 0, n = name.length();
int len = typed.length();
for (int i=0; i<len; i++) {
if (j<n && typed.charAt(i) == name.charAt(j)) {
j++;
}
}
return j == n;
}
04 小結
算法專題目前已連續(xù)日更超過六個月，算法題文章223+篇，公眾號對話框回復【數(shù)據結構與算法】、【算法】、【數(shù)據結構】中的任一關鍵詞，獲取系列文章合集。
以上就是全部內容，如果大家有什么好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發(fā)就是對我最大的回報和支持！
