3ms C++ Solution using bit manipulation


  • 0
    F

    The key is that there are 26 characters and can be represented with 26-bits, so that one 32-int is enough.

        vector<string> findWords(vector<string>& words) {
            vector<string> res;
            vector<string> kb = {"qwertyuiop", "asdfghjkl", "zxcvbnm"};
            vector<int> masks(3);
            for (int i = 0;i < kb.size();i ++) {
                for (auto c: kb[i]) {
                    masks[i] |= 1 << (c >= 'a' ? c - 'a' : c - 'A');
                }
            }
            
            for (auto w: words) {
                int mask = 0;
                for (auto c: w) {
                    mask |= 1 << (c >= 'a' ? c - 'a' : c - 'A');
                }
                for (auto m: masks) {
                    if ((m & mask) == mask) {
                        res.push_back(w);
                        break;
                    }
                }
            }
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.