C# time limited exceed need improvement


  • 0
    Y
    //need to ask questions like:
    // 1. Do we need to trim the start and end spaces?
    // 2. Upcase, low case?
    // 3. null or empty string?
    // 4. do we have any duplications?
    // 5. Are all these strings in the same length?
    
    public class Solution {
        public IList<IList<string>> GroupAnagrams(string[] strs) {
            
            var deffrentLengthList = new Dictionary<int,Dictionary<string,IList<string>>>();
            
            for(int i=0; i<strs.Length; i++)
            {
                if(!deffrentLengthList.ContainsKey(strs[i].Length))
                {
                    var newList=new List<string>(){strs[i]};
                    var newDictionary = new Dictionary<string,IList<string>>();
                    newDictionary.Add(strs[i],newList);
                    deffrentLengthList.Add(strs[i].Length, newDictionary);
                    continue;
                }
                
                bool find = false;
                
                foreach(var existStringKey in deffrentLengthList[strs[i].Length].Keys)
                {
                    if(IsPo(existStringKey,strs[i]))
                    {
                        deffrentLengthList[strs[i].Length][existStringKey].Add(strs[i]);
                        find=true;
                        break;
                    }
                }
                
                if(!find)
                {
                    var newList=new List<string>(){strs[i]};
                    deffrentLengthList[strs[i].Length].Add(strs[i],newList);
                }
            }
            
            var result = new List<IList<string>>();
            
            foreach(var item in deffrentLengthList.Values)
            {
                //var newList=new List<string>();
                result.AddRange(item.Values);
            }
            
            return result;
        }
        
        //test case
        // ab, ba; abb, bba; a,b;
        
        public bool IsPo(string source,string target)
        {
            
            char[] sourceChars=source.ToCharArray(0,source.Length);
            Array.Sort(sourceChars);
            char[] targetChars=target.ToCharArray(0,target.Length);
            Array.Sort(targetChars);
            
            for(int i=0;i<sourceChars.Length;i++)
            {
                if(sourceChars[i]!=targetChars[i])
                    return false;
            }
            
            return true;
            
            var sourceHash = new Dictionary<char,int>();
            
            for(int i=0; i<source.Length; i++)
            {
                if(!sourceHash.ContainsKey(source[i]))
                {
                       sourceHash.Add(source[i],1);
                       continue;
                }
                
                sourceHash[source[i]] += 1;
            }
            
            for(int i=0; i<source.Length; i++)
            {
                if(!sourceHash.ContainsKey(target[i]))
                    return false;
                
                if(sourceHash[target[i]]==0)
                    return false;
                
                sourceHash[target[i]] -= 1;
            }
            
            return true;
            
        }
    }

Log in to reply
 

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