Simple Java Version. Patched for the last test case.


  • 1
    H

    The algorithm is similar. There is a check before each brute force search.

    public class Solution {
        public List<Integer> findSubstring(String s, String[] words) {
            int num = words.length;
            int len = words[0].length();
            List<Integer> res = new ArrayList<>();
            Set<Integer> set = new HashSet<>();
            Map<String, Integer> count = new HashMap<>();
            for (String word : words) {
                count.put(word, count.containsKey(word) ? count.get(word) + 1 : 1) ;
            }
            for (int i = 0; i < s.length() - num * len + 1; ++i) {
                // Check whether it is the same as a checked one.
                String sub1 = s.substring(i >= len ? i - len : 0, i);
                String sub2 = s.substring(i + num * len - len, i + num * len);
                if (sub1.equals(sub2)) {
                    if (set.contains(i - len)) {
                        res.add(i);
                        set.add(i);
                    }
                    continue;
                }
    
                Map<String, Integer> seen = new HashMap<>();
                int j = i;
                for (; j < i + num * len; j += len) {
                    String sub = s.substring(j, j + len);
                    if (! count.containsKey(sub)) {
                        break;
                    } else {
                        seen.put(sub, seen.containsKey(sub) ? seen.get(sub) + 1 : 1);
                    }
                    if (seen.get(sub) > count.get(sub)) break;
                }
                if (j == i + num * len) {
                    res.add(i);
                    set.add(i);
                }
            }
            return res;
        }
    }
    

Log in to reply
 

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