A Short Accepted C# Solution O(m*n)


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

Log in to reply
 

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