520 ms C# Two-Pointer Solution - O(N * Len(word)) with explanations


  • 0
    L

    520ms is the fastest C# solution in OJ so far.

    The idea is to pick up starting point from 0 to Len(word) - 1, so we will take advantage of Hashmap for each starting point in the loop to avoid repeating creating hashmap and clear history data to save time.

    Say we have input pair ("wordgoodgoodgoodbestword", { "word", "good", "best", "good"}), we will loop from starting point of 'w', 'o', 'r' and 'd', and in each loop of starting point, we are checking word by word by using another right point with step of the word's length, so the hashmap will be updated at real time as the right point going ahead.

    Once there is no matching word, the starting point will jump to right point, or word's count exceeding the dictionary's count, starting point will go ahead until hashmap refreshed to have word's count == dictionary's word count.

    Code as follow:

    public IList<int> FindSubstring(string s, string[] words) {
        List<int> result = new List<int>();
        int wordCount = words[0].Length;
        IDictionary<string, int> hist = new Dictionary<string, int>(), currHist = new Dictionary<string, int>();
        foreach (string w in words) hist[w] = hist.ContainsKey(w) ? hist[w] + 1 : 1;
        for (int i = 0; i < wordCount; i++){
            currHist.Clear();
            for (int j = i, k = i; j + words.Length * wordCount <= s.Length; k += wordCount){
                string word = s.Substring(k, wordCount);
                if (!hist.ContainsKey(word)){
                    currHist.Clear();
                    j = k + wordCount;
                    continue;
                }
                currHist[word] = currHist.ContainsKey(word) ? currHist[word] + 1 : 1;
                if (currHist[word] > hist[word])
                    while (currHist[word] > hist[word]){
                        currHist[s.Substring(j, wordCount)]--;
                        j += wordCount;
                    }
                else if ((k - j) / wordCount == words.Length - 1){
                    result.Add(j);
                    currHist[s.Substring(j, wordCount)]--;
                    j += wordCount;
                }
            }
        }
        return result;
    }

Log in to reply
 

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