Ac solution code


  • 0

    The basic idea is using a map to count the amount of each distinct word, and then validate whether the substring starting with i is a concatenation of each word in words.

    Runtime complexity = O(n^2 + wordsSize ) in the Worst Case

    O(wordsSize): Count the amount for each distinct word
    O(n^2): Validate substrings
    
    1) In the Worst Case: all substrings appear in words list, e.g. "aaaaaaaaaaaaaaaaaa...", {"a", "a", "a", "a", "a", "a"... }.    
    2) On average, it will be much faster than O(n^2 + wordsSize ), because once substring doesn't match words list, loop will break.
    

    JAVA Code:

    public List<Integer> findSubstring(String s, String[] words) {
        Map<String, Integer>map = new HashMap<String, Integer>();
        //Runtime = O(wordsSize)
        for (String w : words) map.put(w, map.containsKey(w) ? map.get(w) + 1: 1);// Count the amount for each distinct word
     
        int len = words[0].length(), allLen = len * words.length; 
        List<Integer> res = new LinkedList<Integer>();
        for (int i = 0; i <= s.length() - allLen; i++) {//Runtime = O(n) * O(validate function) = O(n) * O(n) = O(n^2)
            Map<String, Integer>mapTmp = new HashMap<String, Integer>(map);
            if (validate(s, i, len, allLen, mapTmp))// Validate whether the substring starting with i is a concatenation of each word in words 
                res.add(i);
        }
        return res;
    } 
    
    //Runtime = O(n/wordLength * wordLength) = O(n)
    private boolean validate(String s, int i, int len, int allLen, Map<String, Integer>map) {
        for (int j = i; j < i + allLen; j+=len) {//Runtime = O(n/wordLength)
            String str = s.substring(j, j + len);// Runtime = O(wordLength)      
            if (map.get(str) == null) return false;
            int count = map.get(str);
            if (count == 1) map.remove(str);
            else map.put(str, count - 1); 
    
            if (map.isEmpty())// All words are placed concatenately 
                return true;        
        }
        return false;
    }

Log in to reply
 

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