Java Not so optimized solution


  • 0
    V
    class Solution {
        public List<Integer> findSubstring(String s, String[] words) {
            Map<String, Integer> m = new HashMap<>();
            
            for (int i = 0; i < words.length; i++) {
                if (!m.containsKey(words[i])) {
                    m.put(words[i], 1);
                } else m.put(words[i], m.get(words[i]) + 1);
            }
            
            int totalWords = words.length, wordlen = words[0].length();
            List<Integer> result =  new ArrayList<>();
            int lastIndex = s.length() - totalWords * wordlen;
            for(int i = 0; i <= lastIndex; i++) {
                String currStr = s.substring(i, i + wordlen);
                if (m.containsKey(currStr)) {
                    Map<String, Integer> copy = new HashMap<>(m);
                    int matched = 0, last = i;
                    while(copy.containsKey(currStr)) {
                        copy.put(currStr, copy.get(currStr) - 1);
                        if (copy.get(currStr) == 0) copy.remove(currStr);
                        i += wordlen;
                        if (++matched == totalWords) break;
                        currStr = s.substring(i, i + wordlen);
                    }
                    
                    if (matched == totalWords) {
                        result.add(last);
                    }
                    i = last;
                }
            }
            
            return result;
        }
    }
    

Log in to reply
 

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