Java O(n) clear solution


  • 0
    Y

    This problem is straight forward, we scan the whole string for a matching pattern. A map is used to record the number of appearance of each word in the word list, and every time we scan a pattern, we make a new copy of the map and use its size to check whether we have found a pattern or not.

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if(words == null || words.length == 0) {
            return res;
        }
        int n = s.length();
        int m = words.length;
        int k = words[0].length();
        Map<String, Integer> map = new HashMap<>();
        for(String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        
        for(int i = 0; i <= n - k * m; i++) {
            Map<String, Integer> visited = new HashMap<>(map);
            for(int j = 0; j < m; j++) {
                int index = i + j * k;
                String word = s.substring(index, index + k);
                if(visited.containsKey(word)) {
                    visited.put(word, visited.get(word) - 1);
                    if(visited.get(word) == 0) {
                        visited.remove(word);
                    }
                } else {
                    break;
                }
            }
            if(visited.size() == 0) {
                res.add(i);
            }
        }
        return res;
    }

  • 1
    C

    the complex is O(n*m) rather than O(n).


Log in to reply
 

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