Accepted Java O(n) solution using histogram


  • 4
    M
    public List<Integer> findSubstring(String S, String[] L) {
        List<Integer> res = new ArrayList<>();
        if (L.length == 0) {
            return res;
        }
        int len = L[0].length();
        int num = L.length;
        if (len * num > S.length()) {
            return res;
        }
    
        //histogram of words in L
        HashMap<String, Integer> dic = new HashMap<>();
        for (String s : L) {
            if (dic.containsKey(s)) {
                dic.put(s, dic.get(s) + 1);
            } else {
                dic.put(s, 1);
            }
        }
    
        //the word that starts from i in S
        String[] sDic = new String[S.length() - len + 1];
        for (int i = 0; i < sDic.length; i++) {
            String sub = S.substring(i, i + len);
            if (dic.containsKey(sub)) {
                sDic[i] = sub;
            } else {
                sDic[i] = "";
            }
        }
    
        //traverse in order of 0,0+len,...,1,1+len,...len-1,len-1+len...therefore it is O(n) despite of two loops
        for (int i = 0; i < len; i++) {
    
            //start of concatenation
            int start = i;
            //number of words found
            int found = 0;
            //dynamic word histogram of words in substring(start,j);
            HashMap<String, Integer> tempDic = new HashMap<>();
            for (int j = i; j <= S.length() - len; j = j + len) {
                String word = sDic[j];
                if (word.equals("")) {
                    tempDic = new HashMap<>();
                    start = j + len;
                    found = 0;
                    continue;
                } else {
                    if (!tempDic.containsKey(word)) {
                        tempDic.put(word, 1);
                    } else {
                        tempDic.put(word, tempDic.get(word) + 1);
                    }
                    found++;
                }
                //if we over-count a word, delete the first word in front. Also delete the words before that.
                if (tempDic.get(word) > dic.get(word)) {
                    while (!sDic[start].equals(word)) {
                        tempDic.put(sDic[start], tempDic.get(sDic[start]) - 1);
                        start += len;
                        found--;
                    }
                    tempDic.put(word, tempDic.get(word) - 1);
                    start += len;
                    found--;
                }
                if (found == num) {
                    res.add(start);
                }
    
            }
    
        }
        return res;
    }

  • 0
    F

    It is a wonderful solution. Good job.


  • 0
    L

    less space, more time.

    public List<Integer> findSubstring(String s, String[] words) {
            LinkedList<Integer> list = new LinkedList<Integer>();
    
            if(words == null || words.length == 0 || words.length*words[0].length() > s.length()) {
                return list;
            }
    
            int wordLen = words[0].length();
            int wordNum = words.length;
    
            HashMap<String, Integer> wordsMap = new HashMap<String, Integer>(wordNum);
            for(String word : words) {
                wordsMap.put(word, wordsMap.containsKey(word)?wordsMap.get(word)+1:1);
            }
    
            HashMap<String, Integer> curMap = new HashMap<String, Integer>(wordNum);
    
            for(int i = 0; i < wordLen; i++) {
                curMap.clear();
                int pos = i, j = 0;
                for(; i+wordLen*(j+1) <= s.length(); j++) {
                    String curWord = s.substring(i+wordLen*j, i+wordLen*(j+1));
                    if(!wordsMap.containsKey(curWord)) {
                        curMap.clear();
                        pos = i + wordLen*(j+1);
                        continue;
                    }
    
                    curMap.put(curWord, curMap.containsKey(curWord)?curMap.get(curWord)+1:1);
    
                    while(curMap.get(curWord) > wordsMap.get(curWord)) {
                        String headWord = s.substring(pos, pos + wordLen);
                        if(curMap.get(headWord) == 1) {
                            curMap.remove(headWord);
                        } else {
                            curMap.put(headWord, curMap.get(headWord) - 1);
                        }
                        pos += wordLen;
                    }
    
                    if(curMap.equals(wordsMap)) {
                        list.add(pos);
                    }
                }
            }
            return list;
        }

Log in to reply
 

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