[LeetCode]Substring with Concatenation of All Words

一般要找满足条件的substring或者substring的长度想法一般都是双指针，右指针每一次移动一个单位长度，然后左指针根据情况来决定如何移动。已此题为例，由于string的array里可能存在重复的string，所以首先我们需要一个basemap来记录每个string出现的最多次数，一个currmap来记录到目前为止在basemap里的元素那些出现了，出现了多少次，之后还需要一个count的变量来记录是不是string的array里面所有的元素都出现过了，因为有重复元素的话map的size不是array的长度。在这里右指针每次移动的单位步长是string array里string的长度step。根据右指针的移动分以下几种情况：

• 如果[right，right + step]的substring不在basemap中，left到right + step去，因为从left到right + step之前都不能满足要求
• 如果[right，right + step]的substring在basemap中，更新currmap和count之后，如果currmap对应的string出现不大于basemap中的值，看count是否等于string array的长度，等于的话加入结果集
• 如果[right，right + step]的substring在basemap中，更新currmap和count之后，如果currmap对应的string出现大于basemap中的值，左移left直到对应string在currmap的值等于basemap的值，看count是否等于string array的长度，等于的话加入结果集

注意为了不遗漏解，以上过程要从0 - step - 1开始的index全部进行一次，时间复杂度是O(n / step * step) == O(n)，线性时间复杂度，代码如下：

	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 step = L[0].length(), len = S.length(), dictSize = L.length;
	if (step == 0)
	return res;
	HashMap<String, Integer> baseMap = new HashMap<String, Integer>();
	for (int i = 0; i < dictSize; i++) {
	if (!baseMap.containsKey(L[i]))
	baseMap.put(L[i], 1);
	else
	baseMap.put(L[i], baseMap.get(L[i]) + 1);
	}
	//scan each word with length of step
	for (int i = 0; i < step; i++) {
	int count = 0;
	HashMap<String, Integer> currMap = new HashMap<String, Integer>();
	int left = i;
	//right pointer move to the start of next word with length of step
	for (int right = i; right <= len - step; right += step) {
	String curr = S.substring(right, right + step);
	//if word is not in dictionary
	if (!baseMap.containsKey(curr)) {
	count = 0;
	currMap.clear();
	left = right + step;
	//in dictionary
	} else {
	if (!currMap.containsKey(curr))
	currMap.put(curr, 1);
	else
	currMap.put(curr, currMap.get(curr) + 1);
	count++;
	//if num of words exceed the num of word int dictionary, move left until the num of that word decrease by 1
	if (currMap.get(curr) > baseMap.get(curr)) {
	String temp;
	do {
	temp = S.substring(left, left + step);
	currMap.put(temp, currMap.get(temp) - 1);
	if (currMap.get(temp) == 0)
	currMap.remove(temp);
	left += step;
	count--;
	}while(!temp.equals(curr));
	}
	if (count == dictSize)
	res.add(left);
	}
	}
	}
	return res;
	}
	}

view raw Substring with Concatenation of All Words .java hosted with ❤ by GitHub