Heavy OOD C# solution


  • 0
    E

    The solution runs in O(n*(m + kk + k)) where n is the length of strs array, m is the size of a string at 0 <= i < n, and k is a constant 26.
    So my run time is O(n
    m). My algorithm is not efficient for large strings i.e. a big m. If m is small, it approaches O(n) in practice.

    public class Solution {
        public IList<IList<string>> GroupAnagrams(string[] strs) {
            
            var inventoryToWordList = new Dictionary<LetterInventory, IList<string>>();
            
            for(var i = 0; i < strs.Length; i++) {
                var inventory = new LetterInventory(strs[i]);
                if(!inventoryToWordList.ContainsKey(inventory)) {
                    inventoryToWordList.Add(inventory, new List<string>());
    
                }
                inventoryToWordList[inventory].Add(strs[i]);
            }
            
            return inventoryToWordList.Values.Select(wordList => wordList).ToList();
        }
    }
    
    public class LetterInventory 
    {
        char[] _inventory;
    
        public LetterInventory(String str)
        {
            var lowerCaseStr = str.ToLower();
            _inventory = new char[26];
    
            for (var i = 0; i < lowerCaseStr.Length; i++)
            {
                _inventory[lowerCaseStr[i] - 'a']++;
            }
        }
    
        public override bool Equals(Object other)
        {
            var otherInventory = other as LetterInventory;
            if(otherInventory == null)
            {
                return false;
            }
            var otherInventoryList = otherInventory.GetInventory();
    
            for (var i = 0; i < this._inventory.Length; i++)
            {
                if (otherInventoryList[i] != this._inventory[i])
                    return false;
            }
            return true;
        }
    
        public override int GetHashCode()
        {
            var hashCode = 1;
            for (var i = 0; i < this._inventory.Length; i++)
            {
                hashCode += this._inventory[i]*(i+3);
            }
            return hashCode;
        }
    
        public char[] GetInventory()
        {
            return _inventory;
        }
    }
    

Log in to reply
 

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