C# solution with prime number


  • 1
    X

    public class Solution {
    public IList<IList<string>> GroupAnagrams(string[] strs) {

        if (strs == null)
        {
            return null;
        }
        
        int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
        
        Dictionary<long, List<string>> res = new Dictionary<long, List<string>>();
        
        foreach(String x in strs)
        {
            long val = 1;
            
            for(int i= 0; i< x.Length; i++)
            {
                if(x[i]>='a' && x[i]<='z')
                {
                    val *= prime[x[i]-'a'];
                }
            }
            
            List<string> currentValue = null;
            
            if (res.TryGetValue(val, out currentValue))
            {
                currentValue.Add(x);
            }
            else 
            {
                currentValue = new List<string>();
                currentValue.Add(x);
            }
            
            res[val] = currentValue;
        }
        
        IList<IList<string>> result = new List<IList<string>>();
        
        foreach(var pair in res)
        {
            IList<string> values = pair.Value;
            result.Add(values);
        }
        
        return result;
    }
    

    }


  • 0
    H

    Great idea to use the product of prime as the key value of a string.
    This method is suitable for strings that includes 'a' ~ 'z' only.

    public IList<IList<string>> GroupAnagrams(string[] strs)
    {
        if (strs == null)
        {
            return null;
        }
    
        int[] prime = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 41, 43, 47, 53, 59, 
                       61, 67, 71, 73, 79, 83, 89, 97, 101, 103};
    
        var dict = new Dictionary<long, IList<string>>();
    
        foreach (var str in strs)
        {
            long val = 1;
            
            foreach (var ch in str)
            {
                if (ch >='a' && ch <='z')
                {
                    val *= primeTable[ch -'a'];
                }
            }
            
            if (!dict.ContainsKey(val))
            {
                dict.Add(val, new List<string>());
            }
            
            dict[val].Add(str);
        }
        
        return dict.Values.ToList();
    }

Log in to reply
 

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