Using long 64-bit to store the word abbreviation instead of String (Java)


  • 0

    The key point of this question is not only to find unique words, but also how to index the dictionary. Using String to store the index has two issues: (1) the lengths of the keys are different (2) require more space while indexing long words, for exmaple, using the dictionary is used to store the text message not just words. Thus, one way to encode the abbreviation as a 64-bit long int. (see code below)
    In addition, imaging that we are passing a messages via internet using UDP, this index can be used as a header for checking the length, the starting char, and the ending char.

    public class ValidWordAbbr {
    
        Map<Long, String> map = new HashMap();
        private Long encode(String s) {
            int len = s.length();
            if (len >=3) {
                return new Long(  (((long)s.charAt(0)) << 48) | (((long)s.charAt(len-1)) << 32) | (long) len  );
            } else {
                return null;
            }
        }
        public ValidWordAbbr(String[] dictionary) {
            for (String s: dictionary) {
                Long key = encode(s);
                if( key != null) {
                    if ( map.containsKey(key) ) {
                        map.put( key, null);
                    } else {
                        map.put( key, s);
                    }
                }
            }
        }
        public boolean isUnique(String word) {
            Long key = encode(word);
            if ( map.containsKey(key) ) {
                String s = map.get(key);
                if ( s == null ) return false;
                if ( ! s.equals(word) ) return false;
            } 
            return true;
        }
    }

Log in to reply
 

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