Java got TLE on big test case and I dont know why


  • 0
    J
    	public ArrayList<Integer> findSubstring(String s, String[] words) {
    	ArrayList<Integer> res = new ArrayList<Integer>();
        if(s == null || s.length() == 0 || words == null || words.length == 0) {
        	return res;
        }
        HashMap<String, Integer> map = new HashMap<String, Integer>();
        HashSet<Character> set = new HashSet<Character>();
        int blockLength = 0;
        for(int i = 0; i < words.length; i++) {
        	if(!map.containsKey(words[i])) {
        		map.put(words[i], 1);
        	}
        	else {
        		map.put(words[i], map.get(words[i]) + 1);
        	}
        	blockLength = words[i].length();
        	if(!set.contains(words[i].charAt(0))) {
        		set.add(words[i].charAt(0));
        	}
        }
        for(int i = 0; i <= s.length() - words.length * blockLength; i++) {
        	if(set.contains(s.charAt(i))) {
        		String temp = s.substring(i, words.length * blockLength + i );
        		if(equals(temp, words, map)) {
        			res.add(i);
        		}
        		for(int k = 0; k < words.length; k++) {
        			map.put(words[k], 0);
        		}
        		for(int j = 0; j < words.length; j++) {
                	if(!map.containsKey(words[j])) {
                		map.put(words[j], 1);
                	}
                	else {
                		map.put(words[j], map.get(words[j]) + 1);
                	}
                }
        	}
        }
        return res;
    }
    private boolean equals(String s, String[] words, HashMap<String, Integer> map) {
    	int length = words[0].length();
    	for(int i = 0; i < s.length(); i += length) {
    		String temp = s.substring(i, i + length);
    		if(!map.containsKey(temp)) {
    			return false;
    		}
    		else{
    			if(map.get(temp) < 0) {
    				return false;
    			}
    			else {
    				map.put(temp, map.get(temp) - 1);
    			}
    		}
    	}
    	for(int i = 0; i < words.length; i++) {
    		if(map.get(words[i]) != 0) {
    			return false;
    		}
    	}
    	return true;
    }

Log in to reply
 

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