leetcode解题方案--030--Substring with Concatenation of All Words

本文主要是介绍leetcode解题方案--030--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).

分析

这道题真是太恶心了，求出给定字符串的字串开头的位置，这个字串需要满足包含所有给定数组的字符串，且仅出现一次。
注意：
数组中字符串可以重复
给定长字符串可以重复。

先给出一个不考虑数组中字符串重复的解法，和第三题一样

 //当字符串数组不重复时可以用这种方法public static List<Integer> findSubstring1(String s, String[] words) {int n = words[0].length();int total = words.length;List<Integer> list = new LinkedList<>();int header = 0;HashMap<String, Integer> map = new HashMap<>();for (int i = 0; i < total; i++) {map.put(words[i], -1);}int currNum = 0;for (int i = 0; i < s.length(); ) {String current;if (i + n < s.length()) {current = s.substring(i, i + n);} else {current = s.substring(i, s.length());}if (map.containsKey(current)) {if (currNum == 0) {header = i;}if (map.get(current) < header) {//不重复map.put(current, i);currNum++;} else {//有重复header = map.get(current) + n;map.put(current, i);currNum = (i - header) / n + 1;}i = i + n;} else {currNum = 0;i = i + 1;}if (currNum >= total) {list.add(header);currNum = n - 1;map.put(s.substring(header, header + n), -1);header = header + n;}}return list;}