1461. Check If a String Contains All Binary Codes of Size K - Medium

前往題目

想法

• 全部比較一遍?這樣需要$O(2^k \times n \times k)$，太沒效率了

思路

1. 疊代整個s，每次切大小k並嘗試加入Set
2. 利用Set的特性，如果可以在s中找到至少$2^k$個unique element，就代表一定是true

Code

class Solution {
    public boolean hasAllCodes(String s, int k) {
        Set<String> set = new HashSet<>();

        // 最後到-k + 1個以防出界
        for (int i = 0; i < s.length() - k + 1; ++i) {
            // 每次切大小k
            set.add(s.substring(i, i + k));
        }

        // Set中至少要2^k才有可能包含全部
        return set.size() >= Math.pow(2, k);
    }
}