题目描述：
串联所有单词的子串
给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。
注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。
示例 1：
输入： s = "barfoothefoobarman",
words = ["foo","bar"]
输出：[0,9]
解释： 从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar" 。 输出的顺序不重要, [9,0] 也是有效答案。
示例 2：
输入： s = "wordgoodgoodgoodbestword",
words = ["word","good","best","word"]输出：[]
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=30
思路分析：
看到这个题目之后，感觉难度应该算是一般，但是细节上有一些坑需要注意。简单来说，题目给了一个String数组和一个字符串，要求在字符串中找出所有子字符串，其子字符串要包含且仅包含数组里所有的元素各一次。
因为数组中所有元素长度是一致的，所以String数组可以组成一个长度为：
length = 单个元素长度 * 数组长度
的字符串。因此，我们可以从字符串s的最左端开始，循环遍历长度为length的子字符串，如果该子字符串符合要求，即将该起始index存入返回结果。用例子1来举例子：
s = "barfoothefoobarman";
words = ["foo","bar"];
// words中所有元素长度之和为6，所以遍历字符串s的顺序应该是
barfoo
arfoot
rfooth
foothe
oothef
......
barman有了这个思路，接下来就是如何判断每个子字符串是否包含且仅包含数组里所有的元素各一次的问题了。因为子字符串的长度就是数组所有元素长度之和，所以以单个元素的长度为条件循环子字符串，如果子字符串的每一段都对应找到了数组中相同的元素，则表示该子字符串为结果之一。
代码分析：
public List<Integer> findSubstring(String s, String[] words) {
// 定义返回结果
List<Integer> result = new ArrayList<>();
// 如果字符串或数组任意一个为空，那么返回结果也是空。
if (s == null || s.length() == 0 || words.length == 0) {
return result;
}
// 字符串长度
int sLength = s.length();
// 数组中单个元素长度
int wordLength = words[0].length();
// 从字符串s的最左端开始，循环遍历长度为length的子字符串
for (int i = 0; i + wordLength * words.length <= sLength; i++) {
// 取到从第i位开头的长度为数组元素总长度的子字符串
String subString = s.substring(i, i + wordLength * words.length);
// 判断是否为符合条件的flag
boolean isCorrect = true;
// 为了不影响之后的循环，复制一个新数组
String[] wordsTemp = Arrays.copyOf(words, words.length);
// 以数组中单个元素的长度为条件循环该子字符串
for (int j = 0; j + wordLength <= subString.length(); j += wordLength) {
if (!isCorrect) {
break;
}
// 从子字符串中得到长度为数组单个元素长度的孙字符串
String oneWord = subString.substring(j, j + wordLength);
// 循环数组，看数组中是否存在该孙字符串
for (int k = 0; k < wordsTemp.length; k++) {
// 组中存在该孙字符串
if (wordsTemp[k].equals(oneWord)) {
// 因为字符串或数组中可能存在重复String，
// 因此，将已确定存在的数组元素清空
wordsTemp[k] = "";
break;
}
// 如果循环到数组结束仍没找到相同元素，则匹配失败。
if (k == wordsTemp.length - 1) {
isCorrect = false;
}
}
}
// 匹配成功，则将该index存入返回结果
if (isCorrect) {
result.add(i);
}
}
return result;
}本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: https://leetcode.jp/leetcode-30-substring-with-concatenation-of-all-words思路分析及源码分享/