A readable O(N*log(n)) solution


  • 0
    D

    The test cases are quite zealous, especially the last one with the alternating "ab" characters, lol. I was reviewing most of the fast solutions, and, to be frank, most of those are not very readable or easy to follow in my opinion. I could not seeing doing one of those in an 1-hour interview question. I could see discussing optimization, but, not coding it in 1-hour. In 1-hour, I would expect, at least, an O(N^2) solution. After, that, I would do follow-up questions on optimization.

    At any rate, I think my solution is easy enough to explain without confusion. Maintenance can be a big-deal so something that is readable can go a long way in a team-environment.

    However, I still need to give the guys, with the very fast solutions some kudos! Good job guys! Just remember us maintenance folks, please. ;-)


    public class Solution
    {
        public IList<int> FindSubstring(string s, string[] words)
        {
            List<int> indices = new List<int>();
    
            //Only process if we meet criteria
            if (!String.IsNullOrEmpty(s) && words.Length > 0 && words[0].Length > 0 && 
                s.Length >= words.Length * words[0].Length)
            {
                int wordLen = words[0].Length;
                int totalWordLen = words.Length * words[0].Length;
                
                //Iterate through whole string looking for matches
                for (int i = 0; i <= s.Length - totalWordLen; i++)
                {
                    bool isMatched = true;
                    Dictionary<string,int> wordMap = new Dictionary<string, int>(words.Length);
    
                    //Rebuild map for this iteration
                    for (int k=0; k < words.Length; k++)
                    {
                        if (wordMap.ContainsKey(words[k]))//We have a duplicate word
                        {
                            wordMap[words[k]]++;
                        }
                        else
                        {
                            wordMap[words[k]] = 1;
                        }
                    }
                                        
                    //Iterate substring to determine if we have a match
                    for(int j=i; j <= (totalWordLen - wordLen) + i; j += wordLen)
                    {
                        string source = s.Substring(j, wordLen);
    
                        if (wordMap.ContainsKey(source))
                        {
                            if (wordMap[source] == 0)//no more available for match
                            {
                                isMatched = false;
                                break;
                            }
                            
                            wordMap[source]--;
                        }
                        else
                        {
                            isMatched = false;
                            break;
                        }
                    }
    
                    if (isMatched)
                    {
                        indices.Add(i);
                    }
                }
            }
    
            return indices;
        }
    }
    


Log in to reply
 

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