| # | Title | Tag |

| :--- | :--------------------------------------- | :--------------------------------------- |

| 4 | [Median of Two Sorted Arrays][004] | Array, Binary Search, Divide and Conquer |

| 10 | [Regular Expression Matching][010] | String, Dynamic Programming, Backtracking |

| 23 | [Merge k Sorted Lists][023] | Linked List, Divide and Conquer, Heap |

| 25 | [Reverse Nodes in k-Group][025] | Linked List |

| 30 | [Substring with Concatenation of All Words][030] | Hash Table, Two Pointers, String |

| 44 | [Wildcard Matching][044] | String, Dynamic Programming, Backtracking, Greedy |

| 57 | [Insert Interval][057] | Array, Sort |

| 68 | [Text Justification][068] | String |

[030]: https://github.com/Blankj/awesome-java-leetcode/blob/master/note/030/README.md

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).

**Tags:** Hash Table, Two Pointers, String

题意是

如果你同我一样热爱数据结构、算法、LeetCode，可以关注我 GitHub 上的 LeetCode 题解：[awesome-java-leetcode][ajl]

[title]: https://leetcode.com/problems/substring-with-concatenation-of-all-words

[ajl]: https://github.com/Blankj/awesome-java-leetcode

package com.blankj.hard._030;

import java.util.ArrayList;

import java.util.Collections;

import java.util.HashMap;

import java.util.HashSet;

import java.util.List;

import java.util.Map;

import java.util.Set;

public class Solution {

public List<Integer> findSubstring(String s, String[] words) {

int wordsSize = words.length, wordLen = words[0].length(), end = s.length() - wordsSize * wordLen;

if (end < 0) return Collections.emptyList();

Map<String, Integer> countMap = new HashMap<>();

for (String word : words) {

countMap.put(word, countMap.getOrDefault(word, 0) + 1);

}

List<Integer> res = new ArrayList<>();

Set<Integer> ignores = new HashSet<>();

for (int i = 0; i <= end; ++i) {

if (ignores.contains(i)) continue;

Map<String, Integer> findMap = new HashMap<>();

int st = i, count = 0;

List<Integer> ignore = new ArrayList<>();

for (int j = 0; ; ++j) {

int cur = i + j * wordLen;

if (cur + wordLen > s.length()) break;

String word = s.substring(cur, cur + wordLen);

if (countMap.containsKey(word)) {

findMap.put(word, findMap.getOrDefault(word, 0) + 1);

++count;

while (findMap.get(word) > countMap.get(word)) {

ignore.add(st);

String tmp = s.substring(st, st += wordLen);

findMap.put(tmp, findMap.get(tmp) - 1);

--count;

}

if (count == wordsSize) {

ignore.add(st);

res.add(st);

String tmp = s.substring(st, st += wordLen);

findMap.put(tmp, findMap.get(tmp) - 1);

--count;

}

} else {

for (int k = i; k <= cur; k += wordLen) {

ignore.add(k);

}

break;

}

}

ignores.addAll(ignore);

}

return res;

}

public static void main(String[] args) {

Solution solution = new Solution();

System.out.println(solution.findSubstring("wordgoodgoodgoodbestword", new String[]{"word", "good", "best", "good"}));

System.out.println(solution.findSubstring("barfoothefoobarman", new String[]{"foo", "bar"}));

System.out.println(solution.findSubstring("barfoofoobarthefoobarman", new String[]{"bar", "foo", "the"}));

}

}