Easy Java bit manipulation solution


  • 0
    Z

    As an integer has 32 bits, so that we could use each bit to represent a letter.
    For example:
    abcd is ...01111

    so for each word we encoded it to an integer, then we match the word and the keyboard using OR.
    For example we want to know wether a word can be typed using 'abcd', Then:
    abcd is .....01111
    ad is .......01001
    Then we OR 01111 and 01001 still get 01111. But if we have efg, which is .....110000, after OR with abcd, the result is 111111, which is different, then we can tell efg is not a subset of abcd.

    public String[] findWords(String[] words) {
            if( words == null || words.length == 0 ) {
                return new String[0];
            }
            
            List<String> res = new ArrayList<String>();
            
            int[] codes = new int[3];
            codes[0] = encode("qwertyuiop");
            codes[1] = encode("asdfghjkl");
            codes[2] = encode("zxcvbnm");
            
            for(String word : words){
                int code = encode(word);
                for(int i = 0; i < codes.length; i++){
                    int match = code | codes[i];
                    if( match == codes[i] ){
                        res.add( word );
                        break;
                    }
                }
            }
            
            return res.toArray(new String[ res.size() ]);
        }
        
        
        private int encode(String s){
            int res = 0;
            char[] arr = s.toCharArray();
            for( char c : arr ){
                int index = c - 'a';
                res |= 1 << index;
            }
            return res;
        }
    
    

Log in to reply
 

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