Java solution 122ms


  • 0
    R
    Map<Integer,String> wordCache = null;
        Map<String, Integer> map = null;
        public List<Integer> findSubstring(String s, String[] words) {
            int length = getWordLength(words);
            if(length==0){
                return null;
            }
            if(s==null || s.length()==0){
                return null;
            }
            List<Integer> result = new ArrayList();
            wordCache = initWordsCache(s,length);
            map=initStorageMap(words);
            for(int index=0; index<s.length()-(words.length*length)+1;index++){
                if(isAllWordsContinue(s,index,length,words)){
                    result.add(index);
                }
            }
            return result;
        }
    
        private int getWordLength(String[] words){
            if(words==null || words.length==0){
                return 0;
            }
            else{
                return words[0].length();
            }
    
        }
        private boolean isAllWordsContinue(String str, int start, int length, String[] words){
            Map<String, Integer> storageMap = new HashMap<>(map);
            for(int match=0;match<words.length;match++){
                if(start>=str.length()){
                    return false;
                }
                String subString = wordCache.get(start);
                if(storageMap.containsKey(subString)){
                    if(storageMap.get(subString)<0){
                        return false;
                    }
                    storageMap.put(subString, storageMap.get(subString)-1);
                    start+=length;
                }
                else{
                    return false;
                }
            }
            return true;
        }
        private Map<String, Integer> initStorageMap(String[] words){
            map = new HashMap<>();
            for(String word : words){
                if(!map.containsKey(word)){
                    map.put(word,0);
                }
                else{
                    map.put(word,map.get(word)+1);
                }
            }
            return map;
        }
    
        /**
         * use this method to optimize the speed avoid substring the string repeatedly
         * @param str input string
         * @param length the length of a word
         * @return the wordCache
         */
        private Map<Integer,String> initWordsCache(String str, int length){
            Map<Integer,String> cache = new HashMap<>();
            for(int index=0; index<str.length()-length+1;index++){
                cache.put(index,str.substring(index,index+length));
            }
            return cache;
        }

Log in to reply
 

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