C# - optimization - reduce memory cost by using both HashTable and HashSet


  • 0

    A little optimization you can add is to recognize that as soon as 2 words from the dictionary have the same key any calls to test unique for that key can skip checking if there is a word match. You only need to check if there is a word match when the dictionary contains a single word for a given key.

    When building the lookups, on the second encounter of a key move the key from singles to multies where you can drop the word from the key value pair and just store the key in the multies set.

    public class ValidWordAbbr 
    {
        Dictionary<string, string> singles = null;
        HashSet<string> multies = null;
        
        public ValidWordAbbr(string[] dictionary) 
        {
            this.singles = new Dictionary<string,string>();
            this.multies = new HashSet<string>();
            
            foreach (string word in dictionary)
            {
                string key = this.GetKey(word);
                if (this.multies.Contains(key)) continue;
                
                if (this.singles.ContainsKey(key))
                {
                    if (this.singles[key] != word)
                    {
                        // new word with same key -> move to multies
                        this.singles.Remove(key);
                        this.multies.Add(key);
                    }
                }
                else
                {
                    // new key -> add to singles with this word
                    this.singles.Add(key, word);    
                }
            }
        }
    
        public bool IsUnique(string word) 
        {
            string key = this.GetKey(word);
            return !this.multies.Contains(key) && (!this.singles.ContainsKey(key) || this.singles[key] == word);
        }
        
        private string GetKey(string word)
        {
            if (word == null || word.Length < 3) return word;
            return word[0] + (word.Length - 2).ToString() + word[word.Length - 1];
        }
    }
    

Log in to reply
 

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