2135. Count Words Obtained After Adding a Letter

use bit

T: O(n), n is targetWords size

S: O(m), m is startWords size

class Solution {
    public int wordCount(String[] startWords, String[] targetWords) {
        Set<Integer> startSet = new HashSet<>();
        // 建立 start binary in set
        for (String s : startWords) {
            startSet.add(toBinary(s));
        }
        
        int count = 0;
        // 對所有 target 去快速比對 start
        for (String s : targetWords) {
            int targetBinary = toBinary(s);
            // try 26 個字母
            for (int i = 0; i < 26; i++) {
                int charMask = 1 << i;
                // 如果 try 的 char, 符合 target 某個 char
                if ( (targetBinary & charMask) > 0) {
                    // 把這個 char 移掉, 去 startSet 找看看, 找到就是 count++
                    int maybeInStart = targetBinary & ~charMask;
                    if (startSet.contains(maybeInStart)) {
                        count++;
                        break; // find! stop to try
                    }
                }
            }
        }
        return count;
        
    }
    // 因為這題只有 lowercase English letters only. 
    // 所以就 26 位, 用 int 不會 overflow
    // 把字串轉乘 binary 
    private int toBinary(String s) {
        int binary = 0;
        for (char c : s.toCharArray()) {
           binary += (1 << (c - 'a'));
        }
        return binary;
    }
}

/*
Input: startWords = ["ant","act","tack"], 
targetWords = ["tack","act","acti"]
Output: 2

act => acti
act => tack
 x  => act  
 
Input: startWords = ["ab","a"], targetWords = ["abc","abcd"]
Output: 1

ab => abc
x. => abcd
*/