LeetCode.925-長按的名字(Long Pressed Name)

這是悅樂書的第355次更新，第380篇原創

01 看題和準備

今天介紹的是

LeetCode

算法題中

Easy

級别的第

217

題（順位題号是

925

）。你的朋友正在鍵盤上輸入他的名字。 有時，在鍵入字元c時，鍵可能會被長按，鍵入的字元将被輸入1次或更多次。

你檢查鍵盤的鍵入字元。 如果可能是你的朋友姓名，則傳回

True

，其中一些字元（可能沒有）被長按。例如：

輸入：name =“alex”，typed =“aaleex”

輸出：true

說明：'alex'中的'a'和'e'被長按。

輸入：name =“saeed”，typed =“ssaaedd”

輸出：false

說明：'e'必須按兩次，但它不在輸入的輸出中。

輸入：name =“leelee”，typed =“lleeelee”

輸入：name =“laiden”，typed =“laiden”

說明：沒有必要長按任何字元。

注意：

• name.length <= 1000
• typed.length <= 1000
• name和typed的字元是小寫字母。

02 第一種解法

題目的意思是

typed

中的某些字母會在

name

的基礎上重複出現，當然，最理想的狀态是

name

和

typed

完全相等。

想要結果傳回

true

，需要滿足以下條件：

• 對應位置的字母要相等，

  typed

  中對應位置的字母出現次數隻能等于或多于

  name

  中對應的字母。

• name

  中有的字母以及出現次數，

  typed

  中必須有。
• 在沒處理完

  name

  中的字母時，

  typed

  不能已經處理完了。

反之，傳回

false

就是上述三種情況的反例，隻要出現一種就可以直接傳回

false

。

思路：周遊

name

中的字母，并統計目前字母出現的次數，直到遇到不同的字母，接着周遊

typed

中的字母，同樣計數，然後判斷前面我們分析的三種正常情況的反例，如果符合就直接傳回

false

，三種反例都不符合，就将計數重置為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

字元串，統計

typed

中和

name

相等的字母個數，如果最後和

name

的長度相等，就表明

name

中的字母全部都出現在了

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 小結

算法專題目前已連續日更超過六個月，算法題文章223+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。

以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！