前往
大廳
主題

LeetCode - 1461. Check If a String Contains All Binary Codes of Size K 解題心得

Not In My Back Yard | 2021-09-01 00:00:04 | 巴幣 0 | 人氣 146

題目連結:


題目意譯:
給定一個二元字串 s 以及一整數 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 的子字串(如這題),然後對於每個窮舉出的子字串看其對應的編碼是否有出現過。沒有則將該編碼設為「已出現」,並且將出現個數 + 1。

窮舉完之後,判斷出現個數是否等於 2 ^ k 。如果是則代表長度 k 的所有編碼都作為子字串出現於 s 之中了;反之則沒有。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作