Java solution, easy to understand


  • 0
    B
    public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new LinkedList<Integer>();
        if(s == null || s.length() == 0 || words == null ||words.length == 0)
            return res;
        
        int wlen = words[0].length();
        int len = words.length * wlen;
        
        HashMap<String, Integer> hm = new HashMap<String, Integer>();
        for(int j = 0; j < words.length; j++){
            if(hm.containsKey(words[j])){
                hm.put(words[j], hm.get(words[j]) + 1);
            }else{
                hm.put(words[j], 1);
            }
        } 
        
        for(int i = 0; i <= s.length() - len; i++){
            if(isConcat(s.substring(i, i + len), hm , wlen)){
                res.add(i);
            }
        }
        return res;
    }
    
    private boolean isConcat(String s, HashMap<String, Integer> hm, int wlen){
        HashMap<String, Integer> curHm = new HashMap<String, Integer>();
        for(int i = 0; i <= s.length() - wlen; i = i + wlen){
            String tmpStr = s.substring(i, i + wlen);
            if(!hm.containsKey(tmpStr)) return false;
            if(!curHm.containsKey(tmpStr)){
                curHm.put(tmpStr, 1);
            }else{
                if(curHm.get(tmpStr) + 1 > hm.get(tmpStr)) return false;
                curHm.put(tmpStr, curHm.get(tmpStr) + 1);
            }
        }
        return true;
    }
    

    }


  • 0
    C

    when i submit your code, there is a time limited error..


  • 0
    B

    169 / 169 test cases passed.
    Status: Accepted
    Runtime: 158 ms


Log in to reply
 

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