Accepted short Java solution


  • 11
    S

    Hey, guys!

    Actually, there's nothing special in my solution except the comparably short Java code. It's just a simple sliding window approach which is greatly described in other posts.

    In short, we got the source histogram from the dictionary L and build the new histogram for each possible window comparing it with the help of Java's equals method to the source one. Additionally, for the sake of tiny optimization, we check the starting word for being in the dictionary.

    public List<Integer> findSubstring(String S, String[] L) {
        List<Integer> result = new ArrayList<>();
        int size = L[0].length();
        if (L.length == 0 || L[0].isEmpty() || L[0].length() > S.length()) 
            return result;
        Map<String, Integer> hist = new HashMap<>();
        for (String w : L) {
            hist.put(w, !hist.containsKey(w) ? 1 : hist.get(w)+1);
        }
        for (int i = 0; i+size*L.length <= S.length(); i++) {
            if (hist.containsKey(S.substring(i, i+size))) {
                Map<String, Integer> currHist = new HashMap<>();
                for (int j = 0; j < L.length; j++) {
                    String word = S.substring(i+j*size, i+(j+1)*size);
                    currHist.put(word, !currHist.containsKey(word) ? 
                            1 : currHist.get(word)+1);
                }
                if (currHist.equals(hist)) result.add(i);
            }
        }
        return result;
    }
    

    Hope it helps!


  • 0
    D

    The order of these two statements below needs to be adjusted a little bit as if L.length == 0, there won't be any L[0]

    int size = L[0].length();
    if (L.length == 0 || L[0].isEmpty() || L[0].length() > S.length()) 
        return result;

  • 0
    S

    I have been watching your pretty codes for a long time. And I think I made a O(n) solution this time.
    Even though the code is not as concise as yours.

    public class Solution {
        public List<Integer> findSubstring(String S, String[] L) {
            List<Integer> rslt = new ArrayList<Integer>();
    
            // edge case
            if(L.length==0) return rslt;
    
            // initialize k queues and k maps
            int k = L[0].length();
            int queues[] = new int[k];
            List<Map<String, Integer>> maps = new ArrayList<Map<String, Integer>>();
            Map<String, Integer> map_temp = new HashMap<String, Integer>();
            for(int i = 0;i < L.length;i++) setMap(map_temp, L[i]);
            for(int i = 0;i < k;i++) queues[i] = 0;
            for(int i = 0;i < k;i++) maps.add(new HashMap<String, Integer>(map_temp));
    
            // go though S
            for(int i = 0;i <= S.length()-k;i++){
                Map<String, Integer> map = maps.get(i%k); 
                String s = S.substring(i,i+k);
                if(map.containsKey(s)){
                    queues[i%k]++;
                    map.put(s,map.get(s)-1);
                    if(map.get(s)==0) map.remove(s);
                    // find a match
                    if(queues[i%k]==L.length){
                        rslt.add(i-(queues[i%k]-1)*k);
                        setMap(map, S.substring(i-k*(queues[i%k]-1),i-k*(queues[i%k]-1)+k));
                        queues[i%k]--;
                    }
                }else{
                    if(queues[i%k] > 0){
                        if(!s.equals(S.substring(i-k*queues[i%k],i-k*queues[i%k]+k)))
                            while(queues[i%k] > 0){
                                setMap(map, S.substring(i-k*queues[i%k],i-k*queues[i%k]+k));
                                queues[i%k]--;
                            }
                    }
                }
            }
    
            return rslt;
        }
    
        private void setMap(Map<String, Integer> map, String s){
            if(!map.containsKey(s))
                map.put(s,1);
            else
                map.put(s,map.get(s)+1);
            return;
        }
    }
    

  • 0
    K

    I use your code got TLE


  • 0
    J

    i got TLE too.


  • 0
    L

    I'm confused of below equality statement in Java. Doesn't "equals" to compare the pointer only?

        if (currHist.equals(hist)) result.add(i);
    

  • 1
    S

    TLE +1. LOL.


  • 0
    L
    This post is deleted!

  • 0
    T

    Elegant Code! I learnt one liner "hist.put(w, !hist.containsKey(w) ? 1 : hist.get(w)+1);" and use of HashMap default equals from your code, though I think the time complexity can be further improved. Thanks!


  • 0
    L

    map.equals(x) in Java compare the elements in the map, so I think this line is too time costly.


  • 8
    J

    Slightly improved version, so it consistently passes the test cases without getting TLE:

      public List<Integer> findSubstring(String s, String[] words) {
    	List<Integer> ans = new ArrayList<>();
    	if (s == null || words.length == 0) return ans;
    	int n = words.length, wordLen = words[0].length();
        Map<String, Integer> hist = new HashMap<>();
        for (String w : words) {
        	hist.put(w, hist.getOrDefault(w, 0)+1);
        }
    	Map<String, Integer> curHist = new HashMap<>();
        for (int i = 0; i <= s.length() - n*wordLen; i++) {
        	if (hist.containsKey(s.substring(i, i+wordLen))) {
        		curHist.clear();
        		for (int j = 0; j < n; j++) {
        			String word = s.substring(i + j*wordLen, i+(j+1)*wordLen);
        			if (hist.containsKey(word)) {
        				curHist.put(word, curHist.getOrDefault(word, 0) + 1);
        				if (curHist.get(word) > hist.get(word))
        					break;
        			} else 
        				break;
        		}
        		if (hist.equals(curHist)) ans.add(i);
        	}
        }
        return ans;
    } 

  • 0
    S

    Got TLE, but adding a check the sum of words length smaller than string s length would fix the test cases


  • 0
    D

    still got TLE


  • 0
    D

    incorrect answer for
    "barfoofoobarthefoobarman"
    ["bar","foo","the"]


  • 0
    J

    could you post the your AC code?


  • 0
    H

    what is your meaning??
    can you describe in details?


  • 0
    M

    The time complexity has been changed to linear.


  • 0
    I

    still got TLE +1 !!!!!


  • 0
    Z

    I got TLE as well....


  • 0
    T

    @shpolsky

    @shpolsky said in Accepted short Java solution:

    Hey, guys!

    Actually, there's nothing special in my solution except the comparably short Java code. It's just a simple sliding window approach which is greatly described in other posts.

    In short, we got the source histogram from the dictionary L and build the new histogram for each possible window comparing it with the help of Java's equals method to the source one. Additionally, for the sake of tiny optimization, we check the starting word for being in the dictionary.

    public List<Integer> findSubstring(String S, String[] L) {
        List<Integer> result = new ArrayList<>();
        int size = L[0].length();
        if (L.length == 0 || L[0].isEmpty() || L[0].length() > S.length()) 
            return result;
        Map<String, Integer> hist = new HashMap<>();
        for (String w : L) {
            hist.put(w, !hist.containsKey(w) ? 1 : hist.get(w)+1);
        }
        for (int i = 0; i+size*L.length <= S.length(); i++) {
            if (hist.containsKey(S.substring(i, i+size))) {
                Map<String, Integer> currHist = new HashMap<>();
                for (int j = 0; j < L.length; j++) {
                    String word = S.substring(i+j*size, i+(j+1)*size);
                    currHist.put(word, !currHist.containsKey(word) ? 
                            1 : currHist.get(word)+1);
                }
                if (currHist.equals(hist)) result.add(i);
            }
        }
        return result;
    }
    

    Hope it helps!

    it is time limited when I am running?


Log in to reply
 

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