318. Maximum Product of Word Lengths

Link

Solution

這題的整體邏輯很直觀

就是找到words中沒有重複字元的兩個字串，計算字串長度的乘積，並更新最大值結果。

但如何找到words中沒有重複字元的字串，使用了很有技術的方式。

使用alphabets status來記錄 a-z每個字元出現的狀態，若有出現該bit就是 1 反之就是 0

最後要判斷兩word是否有重複字元，就將兩字串的alphabets status 進行 AND運算，即可得知。

T: O(N^2), N = words.length

  public int maxProduct(String[] words) {
        int maxProduct = 0;
        int[] alphabets = new int[words.length];
        
        for(int i = 0; i < words.length; i++){
            for(int j = 0; j < words[i].length(); j++){
                alphabets[i] |= 1 << words[i].charAt(j) - 'a';
            }
        }
        
        for(int i = 0; i < alphabets.length; i++){
            for(int j = 0; j < alphabets.length; j++){
                if((alphabets[i] & alphabets[j]) == 0){
                    maxProduct = Math.max(maxProduct, words[i].length() * words[j].length());
                }
            }
        }
        return maxProduct;
    }