面试算法-37-串联所有单词的子串

本文主要是介绍面试算法-37-串联所有单词的子串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串长度相同。

s 中的串联子串是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

例如，如果 words = [“ab”,“cd”,“ef”]，那么 “abcdef”， “abefcd”，“cdabef”， “cdefab”，“efabcd”，和 “efcdab” 都是串联子串。 “acdbef” 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以任意顺序返回答案。

示例 1：

输入：s = “barfoothefoobarman”, words = [“foo”,“bar”]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 “barfoo” 开始位置是 0。它是 words 中以 [“bar”,“foo”] 顺序排列的连接。
子串 “foobar” 开始位置是 9。它是 words 中以 [“foo”,“bar”] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

解

class Solution {public List<Integer> findSubstring(String s, String[] words) {int wordLen = words[0].length();int len = words.length;int allLen = wordLen * len;Map<String, Integer> map = new HashMap<>();for (String word : words) {map.put(word, map.getOrDefault(word, 0) + 1);}List<Integer> result = new ArrayList<>();for (int i = 0; i < s.length() - allLen + 1; i++) {int j = 0;Map<String, Integer> tempMap = new HashMap<>();while (j < allLen) {String sub = s.substring(i + j, i + j + wordLen);tempMap.put(sub, tempMap.getOrDefault(sub, 0) + 1);j += wordLen;}if (tempMap.equals(map)) {result.add(i);}}return result;}
}