leetcode-30. Substring with Concatenation of All Words

本文主要是介绍leetcode-30. Substring with Concatenation of All Words，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

leetcode-30. Substring with Concatenation of All Words

题目：

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:
s: “barfoothefoobarman”
words: [“foo”, “bar”]

You should return the indices: [0,9].
(order does not matter).

O(KN)解法1

这题其实算不上难题。至少是难题中比较简单的。
基本思路就是由于words中的String的长短是一样的，那这样就有比较简单的解法，就是用i从0开始向右移动，找substring(0,words[0],length())是否包含在words中就好。当然针对每个i都需要新建一个hashset，并将words中所有string放进去，每找到一个就删除一个，然后迭代判断直到这个hashset为空为止。
这个思路没什么问题的，我也是照这样做的，但是后来还是出错了，因为words会有重复的情况。所以这种情况下只有用HashMap代替HashSet才行。不过今天时间有点紧，就不写了。
从讨论里找到了两种做法一种就是上面这中做法。。还有一种比较麻烦的做法，也贴出来。两种的复杂度应该都是O（KN）N是S的长度，K是words的长度。应该是比较类似的。个人比较倾向于第一种写法。

public class Solution {public 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 wordMap<String, Integer> map = new HashMap<String, Integer>(); // map for Lfor (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 matchString str = S.substring(i + j*len, i + j*len + len); // next wordif (copy.containsKey(str)) { // is in remaining wordsint count = copy.get(str);if (count == 1) copy.remove(str);else copy.put(str, count - 1);if (copy.isEmpty()) { // matchesres.add(i);break;}} else break; // not in L}}return res;}
}

上面就是我之前解释的方法，这里HashMap的建立非常简洁值得借鉴，但是后面for循环其实写的逻辑比较复杂，如果可以写个helper的话程序的思路要清晰的多。
答案来源

O(KN)解法2

public class Solution {// Sliding Window    360ms// ask interviewer if words is empty, should I return empty listpublic List<Integer> findSubstring(String S, String[] L) {List<Integer> res = new LinkedList<>();if (L.length == 0 || S.length() < L.length * L[0].length())   return res;int N = S.length(), M = L.length, K = L[0].length();Map<String, Integer> map = new HashMap<>(), curMap = new HashMap<>();for (String s : L) {if (map.containsKey(s))   map.put(s, map.get(s) + 1);else                      map.put(s, 1);}String str = null, tmp = null;for (int i = 0; i < K; i++) {int count = 0;  // remark: reset count for (int l = i, r = i; r + K <= N; r += K) {str = S.substring(r, r + K);if (map.containsKey(str)) {if (curMap.containsKey(str))   curMap.put(str, curMap.get(str) + 1);else                           curMap.put(str, 1);if (curMap.get(str) <= map.get(str))    count++;while (curMap.get(str) > map.get(str)) {tmp = S.substring(l, l + K);curMap.put(tmp, curMap.get(tmp) - 1);l += K;if (curMap.get(tmp) < map.get(tmp)) count--;}if (count == M) {res.add(l);tmp = S.substring(l, l + K);curMap.put(tmp, curMap.get(tmp) - 1);l += K;count--;}}else {curMap.clear();count = 0;l = r + K;}}curMap.clear();}return res;}
}