Java Hashmap solution 2 pointers..


  • 0
    Y
    public class Solution {
        public List<Integer> findSubstring(String s, String[] words) {
            Map<String,Integer> map = new HashMap<String,Integer>();
            for(String word:words){
                if(map.containsKey(word)){
                    map.put(word,map.get(word)+1);
                }else{
                    map.put(word,1);
                }
            }
            int length = words[0].length();
            List<Integer> result = new ArrayList<Integer>();
            for(int i=0;i<length;i++){
                //just start from different point...
                Map<String,Integer> tmp = new HashMap<String,Integer>();
                int start = i;
                int count = 0;
                for(int j=i;j+length<=s.length();j+=length){
                    String word = s.substring(j,j+length);
                    if(map.containsKey(word)){
                        tmp.put(word,tmp.getOrDefault(word,0)+1);
                        count+=1;
                        while(tmp.get(word)>map.get(word)){ //At most greater than zero..
                            String removeWord = s.substring(start,start+length);
                            if(tmp.get(removeWord)>1){
                                //greater than 0..
                                tmp.put(removeWord,tmp.get(removeWord)-1);
                            }else{
                                tmp.remove(removeWord);
                            }
                            start+=length;
                            count-=1;
                            if(removeWord.equals(word))
                                break;
                        }
                        if(count==words.length)
                            result.add(start);
                    }else{
                        tmp.clear();
                        count = 0;
                        start = j+length;
                    }
                }
            }
            return result;
        }
    }

Log in to reply
 

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