C# - simple solution, time O(n * wordLen) and space O(words)


  • 1
    A
    public IList<int> FindSubstring(string s, string[] words) 
    {
        List<int> list = new List<int>();
        if(String.IsNullOrEmpty(s) || words == null || words.Length == 0) return list;
        
        Dictionary<string, int> dict = new Dictionary<string, int>();
        foreach(string w in words) 
        {
            if(!dict.ContainsKey(w)) dict[w] = 1;
            else dict[w]++;
        }
        
        Dictionary<string, int> savedDict = new Dictionary<string, int>(dict);
        int wLen = words[0].Length;
        for(int i = 0; i <= s.Length - words.Length * wLen; i++)
        {
            int j = 0;
            for(; j < words.Length; j++)
            {
                string w = s.Substring(i + j * wLen, wLen);
                
                if( !dict.ContainsKey(w)) break;
                else if( --dict[w] < 0 ) break;
            }
            if(j == words.Length) list.Add(i);
            
            dict = new Dictionary<string, int>(savedDict);
        }
        
        return list;
    }

Log in to reply
 

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