Verbose Java AC solution in 39ms


  • 0
    W

    It's not quite efficient as the other solutions, mainly the way of maintaining a frequency count could be improved to the more elastic sliding window approach.
    Comparing HashMap to HashMap is also slow.. but hey it still works..

    import java.util.*;
    
    class Solution {
        private String getWord(char[] a, int i, int zw){
            char[] out = Arrays.copyOfRange(a, i, i+zw);
            return new String(out);
        }
    
        static class FrequencyMap {
            HashMap<String, Integer> m;
            FrequencyMap() {
                m = new HashMap<>();
            }
            void add(String s) {
                if (m.containsKey(s)) {
                    m.put(s, m.get(s) + 1);
                } else {
                    m.put(s, 1);
                }
            }
            boolean matches(FrequencyMap m2){
                if (m.size() != m2.m.size()) return false;
                for (String s : m.keySet()) {
                    if (!m2.m.containsKey(s)) return false;
                    if (!m.get(s).equals(m2.m.get(s))) return false;
                }
                return true;
            }
            static FrequencyMap count(String[] words) {
                FrequencyMap m = new FrequencyMap();
                for (String w : words) {
                    m.add(w);
                }
                return m;
            }
            boolean has(String w){
                return m.containsKey(w);
            }
            void remove(String w) {
                if (m.containsKey(w) && m.get(w).equals(0)){
                    m.remove(w);
                } else if (m.containsKey(w) && m.get(w) > 0) {
                    m.put(w, m.get(w)-1);
                }
            }
        }
    
        public List<Integer> findSubstring(String s, String[] words) {
            List<Integer> out = new ArrayList<>();
            int dict_size = words.length;
            if (dict_size == 0) return out;
            int word_size = words[0].length();
    
            FrequencyMap fm = FrequencyMap.count(words);
    
            char[] a = s.toCharArray();
            int last_word_begin = a.length - word_size;
    
            String[] word_at = new String[last_word_begin+1];
    
            for (int i=0;i<=last_word_begin;i++) {
                String w = getWord(a, i, word_size);
                if (fm.has(w)){
                    word_at[i] = w;
                }
            }
    
            FrequencyMap[] c = new FrequencyMap[word_size];
            for (int i=0;i<word_size;i++){
                c[i] = new FrequencyMap();
            }
    
            int last_checkpoint = a.length - word_size*dict_size;
    
            for (int i=0;i<word_size;i++) {
                if (i+ word_size * dict_size > a.length) break;
                for (int j=i;j<(i+ word_size*dict_size);j+=word_size) {
                    if (word_at[j] != null) {
                        c[i].add(word_at[j]);
                    }
                }
                for (int j=i;j<=last_checkpoint;j+=word_size) {
                    if (fm.matches(c[i])) {
                        out.add(j);
                    }
                    int window_begin = j;
                    int window_end = j+ word_size * dict_size;
                    if (j>=last_checkpoint || window_end > last_word_begin) break;
    
                    // Update window's frequency map.
                    c[i].remove(word_at[window_begin]);
                    String nex = word_at[window_end];
                    if (nex != null) {
                        c[i].add(nex);
                    }
                }
            }
    
            return  out;
        }
    }
    

Log in to reply
 

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