easy to understand


  • 1
    Y

    public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> list = new ArrayList<>();
    if (s == null || s.length() ==0 || words == null || words.length == 0 || s.length() < words.length * words[0].length()) {
    return list;
    }
    HashMap<String, Integer> map = new HashMap<>();
    for (String word : words) {
    map.put(word, map.containsKey(word) ? map.get(word) + 1 : 1);
    }
    int size = words[0].length();
    int totalLen = s.length();
    int strLen = words.length;

        for (int i = 0; i <= totalLen - size * strLen; i++) {
    
            if (map.containsKey(s.substring(i, size + i ))) {
                HashMap<String, Integer> tmpMap = new HashMap<>();
                int j = 0;
                for(; j < strLen; j++) {
                    String tmpStr = s.substring(i + j * size, i + (j + 1) * size);
                    if (map.containsKey(tmpStr)) {
                        boolean flag = tmpMap.containsKey(tmpStr);
                        int count = 0;
                        if (flag) {
                            count  =  tmpMap.get(tmpStr);
                        }
                        if ( flag && count >= map.get(tmpStr)) {
                            break;
                        }
                        tmpMap.put(tmpStr, flag ? count + 1 : 1);
                    } else {
                        break;
                    }
                }
                if (j == strLen) {
                    list.add(i);
                }
            }
        }
        return list;
    }
    

    }

    • list item

  • 0
    J

    @yws_tracy

    Hey, interesting. I had almost exactly the same idea. I used a Dictionary instead of a HashSet (HashMap in Java) to account for the possibility of repeats, but it's neat to see something so close to the way I considered it. How fast was yours? Mine was relatively slow; almost a second and faster than only 20% of the accepted C# solutions. Anyhow, great job.

    public class Solution {
    	public IList<int> FindSubstring(string s, string[] words) {
    
    		
    		var l = new List<int>();
    		
    		var x = words[0].Length;
    		var y = words.Length;
    		var z = x * y;
    		
    		var dict = new Dictionary<string, int>();
    		
    		int wc = 0;
    		
    		foreach(var w in words)
    		{
    			wc++;
    			if (!dict.ContainsKey(w))
    			dict.Add(w, 1);
    			else
    			dict[w]++;
    		}
    		
    		var cDict = new Dictionary<string, int>(dict);
    				
    		for(int i = 0; i < s.Length-z+1; i++)
    		{	
    			int j = wc;
    			int k = i;
    			while(j > 0) {
    				var p = s.Substring(k, x);
    				if (dict.ContainsKey(p)) {
    					if (dict[p] > 0) {
    						dict[p] -= 1;
    						k+=x;
    						if (j == 0)
    							l.Add(i);
    					}
    					else break;
    				}
    				else break;
    				
    			}
    
    			dict = new Dictionary<string, int>(cDict);		
    			
    		}
    
    		return l;
    	}
    }
    

Log in to reply
 

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