題目連結(jié):
題目意譯:
給定一個二元字串 s 以及一整數(shù) k 。
回傳真(True)如果每個長度為 k 的二進位編碼為 s 的一個子字串。反之,回傳假(False)。
限制:
1 ≦ s.length ≦ 5 × 10 ^ 5
s[i] 只會是 '0' 或是 '1' 。
1 ≦ k ≦ 20
範例測資:
範例 1:
輸入: s = "00110110", k = 2
輸出: true
解釋: 長度為 2 的二進位編碼為 "00" 、 "01" 、 "10" 和 "11" 。它們依序可以在索引值 0 、 1 、 3 、 2 之子字串找到。
範例 2:
輸入: s = "00110", k = 2
輸出: true
範例 3:
輸入: s = "0110", k = 1
輸出: true
解釋: 長度為 1 的二進位編碼為 "0" 和 "1" ,很明顯地兩者皆作為子字串存在於其中。
範例 4:
輸入: s = "0110", k = 2
輸出: false
解釋: 二進位編碼 "00" 長度為 2 且不存在於陣列中。
範例 5:
輸入: s = "0000000001011100", k = 4
輸出: false
解題思維:
窮舉出所有長度為 k 的子字串(如
這題),然後對於每個窮舉出的子字串看其對應(yīng)的編碼是否有出現(xiàn)過。沒有則將該編碼設(shè)為「已出現(xiàn)」,並且將出現(xiàn)個數(shù) + 1。
窮舉完之後,判斷出現(xiàn)個數(shù)是否等於 2 ^ k 。如果是則代表長度 k 的所有編碼都作為子字串出現(xiàn)於 s 之中了;反之則沒有。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。