BitMask 相关

318. Maximum Product of Word Lengths

Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.

 Example 1:

Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".

Example 2:

Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".

Example 3:

Input: words = ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words. 

Constraints:

• 2 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] consists only of lowercase English letters.

暴力解法

class Solution {
    public int maxProduct(String[] words) {
        int max = 0;
        for(int i=0;i){
            for(int j=i+1;j){
                if(!hasCommon(words[i],words[j]))
                    max = Math.max(max,words[i].length()*words[j].length());
            }
        }
        return max;
    }
    private boolean hasCommon(String w1,String w2){
        for(char c : w1.toCharArray()){
            if(w2.indexOf(c)>=0) return true;
        }
        return false;
    }
}

巧用bitmask，将 字符串比对 过程从O(len2) 到 O(1)， 最终时间复杂度： O(N*N+L) N为字符串个数，L为字符串长度

class Solution {
    public int maxProduct(String[] words) {
        int max = 0;
        int[] state = new int[words.length];
        for(int i=0;i){
            state[i] = getState(words[i]);
        }
        for(int i=0;i){
            for(int j=i+1;j){
                if( (state[i] & state[j]) ==0 )
                    max = Math.max(max,words[i].length()*words[j].length());
            }
        }
        return max;
    }
    private int getState(String str){
        int mask = 0;
        for(char c:str.toCharArray()){
            int pos = c-'a';
            mask |= 1<<(pos);
        }
        return mask;
    }
}

bitmask 基础上增加 map对重复字符串集合进行去重，减少比对次数

class Solution {
    public int maxProduct(String[] words) {
        int max = 0;
        Map map = new HashMap();
        
        for(int i=0;i){
            int bitValue = getState(words[i]);
            map.put(bitValue, Math.max(map.getOrDefault(bitValue,0), words[i].length()));
        }
        int result = 0;
        for(int i:map.keySet()){
            for(int j:map.keySet()){
                if( i!=j && ( (i & j) == 0))
                result = Math.max(result, map.get(i)*map.get(j));
            }
        }
        return result;
    }
    private int getState(String str){
        int mask = 0;
        for(char c:str.toCharArray()){
            int pos = c-'a';
            mask |= 1<<(pos);
        }
        return mask;
    }
}

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

Given a binary string s and an integer k, return true if every binary code of length k is a substring of s. Otherwise, return false.

Example 1:

Input: s = "00110110", k = 2
Output: true
Explanation: The binary codes of length 2 are "00", "01", "10" and "11". They can be all found as substrings at indices 0, 1, 3 and 2 respectively.

Example 2:

Input: s = "0110", k = 1
Output: true
Explanation: The binary codes of length 1 are "0" and "1", it is clear that both exist as a substring. 

Example 3:

Input: s = "0110", k = 2
Output: false
Explanation: The binary code "00" is of length 2 and does not exist in the array.

Constraints:

• 1 <= s.length <= 5 * 105
• s[i] is either '0' or '1'.
• 1 <= k <= 20

关键点：使用二进制移位，保持滑动窗口的值 

class Solution {
    public boolean hasAllCodes(String s, int k) {
        int len = 1<<k;
        boolean[] stats = new boolean[len];
        int allOne = len-1;
        int curr = 0;
        for(int i=0;i){
            int flag = s.charAt(i)-'0';
            curr = ( (curr<<1) & allOne ) + flag;
            if(i>=k-1){
                stats[curr] = true;   
            }
        }
        for(int i=0;i){
            if(!stats[i]) return false;
        }
        return true;
    }
}

class Solution {
    public boolean hasAllCodes(String s, int k) {
        int len = 1<<k;
        boolean[] stats = new boolean[len];
        int allOne = len-1;
        int curr = 0;
        for(int i=0;i){
            int flag = s.charAt(i)-'0';
            curr = ( (curr<<1) & allOne ) + flag;
            if(i>=k-1 && !stats[curr]){
                len--;
                stats[curr] = true;
                if(len==0) return true;
            }
        }
        return false;
    }
}