Simple Java solution 35ms


  • 0
    M
    class Solution {
        public List<Integer> findSubstring(String s, String[] words) {
            List<Integer> indexes = new LinkedList<>();
            Map<String, Integer> wordCount = new HashMap<>();
            for (String word : words) {
                if (!wordCount.containsKey(word)) {
                    wordCount.put(word, 0);
                }
                wordCount.put(word, wordCount.get(word)+1);
            }
    
            int len = words[0].length();
            for (int i = 0; i < len; i++) {
                Map<String, Integer> removeMap = new HashMap<>(wordCount);
                int total = words.length;
                int begin = i;
                for (int j = i; j+len-1 < s.length(); j+=len) {
                    String word = s.substring(j, j+len);
                    if (removeMap.containsKey(word) && removeMap.get(word) > 0) {
                        removeMap.put(word, removeMap.get(word)-1);
                        total -= 1;
                    } else {
                        int k = begin;
                        while (!s.substring(k, k+len).equals(word) && k < j) {
                            removeMap.put(s.substring(k, k+len), removeMap.get(s.substring(k, k+len))+1);
                            k += len;
                            total += 1;
                        }
                        begin = k + len;
                    }
    
                    if (total == 0) {
                        indexes.add(begin);
                    }
                }
            }
    
            return indexes;
        }
    }
    

Log in to reply
 

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