Simple Java Solution with Two Pointers and Map


  • 48
    F

    My idea is pretty simple. Just build a map for the words and their relative count in L. Then we traverse through S to check whether there is a match.

    public static List<Integer> findSubstring(String S, String[] L) {
        List<Integer> res = new ArrayList<Integer>();
        if (S == null || L == null || L.length == 0) return res;
        int len = L[0].length(); // length of each word
        
        Map<String, Integer> map = new HashMap<String, Integer>(); // map for L
        for (String w : L) map.put(w, map.containsKey(w) ? map.get(w) + 1 : 1);
        
        for (int i = 0; i <= S.length() - len * L.length; i++) {
            Map<String, Integer> copy = new HashMap<String, Integer>(map);
            for (int j = 0; j < L.length; j++) { // checkc if match
                String str = S.substring(i + j*len, i + j*len + len); // next word
                if (copy.containsKey(str)) { // is in remaining words
                    int count = copy.get(str);
                    if (count == 1) copy.remove(str);
                    else copy.put(str, count - 1);
                    if (copy.isEmpty()) { // matches
                        res.add(i);
                        break;
                    }
                } else break; // not in L
            }
        }
        return res;
    }
    

    At first I was gonna to use a set for words. Owing to the fact that duplicate is allowed in L, we need to use map instead.


  • -4
    A
    public static  List<Integer>	 findSubString(String s ,String [] L) {
    	List<Integer> list = new ArrayList<Integer>();
    	if(s==null|| s==""||L==null||L[0].length()==0)
    		return list;
    	Map<String, Integer> map = new   HashMap<String ,Integer>();
    	int len=L[0].length();
    	for (String  tmp : L) {
    		if(!map.containsKey(tmp)) {
    			map.put(tmp, 1);
    		}
    	}
    	for (int i = 0; i <s.length()-L.length*len; i++) {
    		Map<String , Integer> copy = new HashMap<>(map);
    		for(int j=0;j<L.length;j++) {
    			String tmp_stringString = s.substring(i+j*len, i+j*len+len);
    			if (copy.containsKey(tmp_stringString)) {
    				copy.remove(tmp_stringString);
    			}else {
    				continue;
    			}
    		}
    		if (copy.isEmpty()) {
    			list.add(i);
    		}
    	}
    	return list;
    }
    

    the same way use List can save about 50% time


  • 0
    J

    I dont think this is two pointer ways, it is simply iteration the string


  • 1
    Y

    There are i and j, which are the two pointers. Two pointers can go from either direction. This is the sliding window version.


  • 7
    S

    you code can't pass now, maybe there are some new test cases. Time limit exceeded.


  • 0

    yes. I got “Time limit exceeded” too by the same algorithm T^T


  • 0
    J

    Yes, I also got TLE. I applied the same algorithm to Minimum Subarray Sum and got TLE. What is the problem with this method?


  • 1
    H

    @jocelynayoga I think the copy.remove() is time-consuming, and it's called whenever a substring matches the strings of words. The method should be replaced be checking if the string's count is less than 1. my code with a similar logic got AC with this improvement.


  • 0
    S

    @hizhaojun Hi, hizhaojun, could you please share your AC code? I have tried to replace copy.remove() by checking if the string's count is less than 1, but still got TLE. Thank you.


  • 7
    H

    @SherryH hope it help.

    public class Solution {
        public List<Integer> findSubstring(String s, String[] words) {
        	int n = words.length, m = words[0].length();
        	List<Integer> res = new ArrayList();
            /*Store string array with hashtable.*/
            HashMap<String, Integer> map = new HashMap();
            for (String str : words) {
            	if (map.containsKey(str)) map.put(str, map.get(str)+1);
            	else map.put(str, 1);
            }
            /*m is the length of each word in array words, each time get a substring of length m to check if it exits in words*/
            for (int i = 0; i <= s.length()-n*m; i++) {
                HashMap<String, Integer> copy = new HashMap(map);
            	/*if it exits, use another hashset to avoid duplicate and count the number to reach n, the number of words in array words*/
            	int k = n, j = i;
            	while (k > 0) {
            		String str = s.substring(j, j+m);
            		if (!copy.containsKey(str) || copy.get(str) < 1) break;
            		copy.put(str, copy.get(str)-1);
            		k--; j+=m;
            	}
            	if (k == 0) res.add(i);
            }
            return res;
        }
    }
    

  • 0
    S

    @hizhaojun Hi, thank you so much for your answer. It's strange that now my code also got accepted even though I didn't change anything. :)


  • 1
    Z

    Can anyone clarify the time complexity? I think it is O(N ^ 2),
    and N = len(S) / (each word len).


  • 0

    @zfuuuuu I think so. It's very intuitive. But it seems like it cannot pass the large test case?


  • 0
    T

    I got TLE error with this solution, how can I fix it?


  • 0
    C

    cause judge HashMap copy isEmpty() runs too many times,i try to remove it to the outside of loop,then it works.
    code revise as list:
    public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
    List<Integer> res=new ArrayList<Integer>();
    int len=words[0].length();
    if(s.length()==0||words.length==0) return res;
    Map<String,Integer> map= new HashMap<>();
    for(String str:words)
    map.put(str,(map.containsKey(str)?map.get(str)+1:1));
    for(int i=0;i<=s.length()-lenwords.length;i++){
    Map<String,Integer> cpy=new HashMap<>(map);
    for(int j=0;j<words.length;j++){
    String str=s.substring(i+len
    j,i+len*j+len);
    if(cpy.containsKey(str)){
    int index=cpy.get(str);
    if(index==1) cpy.remove(str);
    else cpy.put(str,index-1);
    }
    else break;
    }
    if(cpy.isEmpty()){
    res.add(i);
    }
    }
    return res;
    }
    }


  • 0
    H

    For those who get Time Limit Exceeded, see my optimized version. link text


  • -1
    D

    @hizhaojun said in Simple Java Solution with Two Pointers and Map:

    int n = words.length, m = words[0].length();
    List<Integer> res = new ArrayList();
    /Store string array with hashtable./
    HashMap<String, Integer> map = new HashMap();
    for (String str : words) {
    if (map.containsKey(str)) map.put(str, map.get(str)+1);
    else map.put(str, 1);
    }
    /m is the length of each word in array words, each time get a substring of length m to check if it exits in words/
    for (int i = 0; i <= s.length()-n*m; i++) {
    HashMap<String, Integer> copy = new HashMap(map);
    /if it exits, use another hashset to avoid duplicate and count the number to reach n, the number of words in array words/
    int k = n, j = i;
    while (k > 0) {
    String str = s.substring(j, j+m);
    if (!copy.containsKey(str) || copy.get(str) < 1) break;
    copy.put(str, copy.get(str)-1);
    k--; j+=m;
    }
    if (k == 0) res.add(i);
    }
    return res;

    I am still getting Time Limit exceed error error with this code for following input
    "abababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababababab"
    ["ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba","ab","ba"]


  • 0
    Y

    Easy to understand. good solution.


  • 0
    V

    I got a TLE for the similiar solution.


Log in to reply
 

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