題目

解題概念

  • 此題簡單來說，就是將words陣列的每個字取出，並去對照是否為 s 字串的 Subsequences (子序列)，最後回傳 Subsequence 的數量
    • 定義 : s 之中，依照由左到右的順序，挑幾個字母出來，就是 s 的 Subsequence
  • 在前置處理中，因為 words 中會有重複的 word，所以要先把 words 陣列轉換成 Dictionary : {word, 數量}
  • 而在主要 while loop 中，比較方式為 :
    1. 若 s[i] 與 word[j] 相等 :
      • 代表這兩個字相等，i 與 j 便各加 1
    2. 若 s[i] 與 word[j] 相等 :
      • 代表這兩個字不相等，j 加 1即可
  • 若最後 j == word_length，代表已將 word 瀏覽過了，而 word 為 s 的 Subsequence

實際寫Code

  • 目標函式 : numMatchingSubseq(s, words)
    • Input : s: str、words: List[str]
    • Output : int
  • 前置作業 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    word_dict = {}
    for word in words : # 將 words 轉換為 Dictionary

        # 若 word_dict 中已有 word，則該 word 的 value 加 1
        if word_dict.get(word):
            word_dict[word] += 1

        # 若 word_dict 中未有 word，則該 word 的 value 設為 1
        else :
            word_dict[word] = 1
  • 主要 for 迴圈部分 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    ans = 0
    for word in word_dict :

        word_index = 0
        word_len = len(word)
        s_index = 0
        s_len = len(s)
        
        # 跑 while loop ，直到 word 搜尋完 or s 搜尋完
        while word_index != word_len and s_index != s_len : 

            # 若兩字相等，則繼續對 word 往後搜尋
            if word[word_index] == s[s_index] :
                word_index += 1
            s_index += 1

        # 若已瀏覽過 word，代表 word 為 s 的 Subsequence 
        if word_len == word_index :

            # 將 word 在 Dictionary 中的 value 加到 ans 中
            ans += word_dict[word]
                
    return ans

參考資料

  1. Longest Increasing Subsequence