【030-Substring with Concatenation of All Words（串联全部单词的子串）】
【LeetCode-面试算法经典-Java实现】【全部题目文件夹索引】
原题
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).
题目大意
给定一个字符串s和一个字符串数组words，wrods中的字符串长度都相等。找出s中全部的子串恰好包括words中全部字符各一次，返回子串的起始位置。
解题思路
把words转化为一个HashMap
代码实现
算法实现类
import java.util.*;
public class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> list = new ArrayList<Integer>();
if (words.length == 0) return list;
int wLen = words[0].length();
int len = s.length();
if (len < wLen * words.length) return list;
Map<String, Integer> mapW = new HashMap<String, Integer>();
for (String word : words)
mapW.put(word, mapW.containsKey(word) ? mapW.get(word) + 1 : 1);
for (int start = 0; start < wLen; start++) {
int pos = start;
int tStart = -1;
Map<String, Integer> mapT = new HashMap<String, Integer>(mapW);
while (pos + wLen <= len) {
String cand = s.substring(pos, pos + wLen);
if (!mapW.containsKey(cand)) {
if (tStart != -1) mapT = new HashMap<String, Integer>(mapW);
tStart = -1;
} else if (mapT.containsKey(cand)) {
tStart = tStart == -1 ? pos : tStart;
if (mapT.get(cand) == 1) mapT.remove(cand);
else mapT.put(cand, mapT.get(cand) - 1);
if (mapT.isEmpty()) list.add(tStart);
} else {
while (tStart < pos) {
String rCand = s.substring(tStart, tStart + wLen);
if (cand.equals(rCand)) {
tStart += wLen;
if (mapT.isEmpty()) list.add(tStart);
break;
}
tStart += wLen;
mapT.put(rCand, mapT.containsKey(rCand) ? mapT.get(rCand) + 1 : 1);
}
}
pos += wLen;
}
}
return list;
}
}
评測结果
点击图片，鼠标不释放，拖动一段位置，释放后在新的窗体中查看完整图片。
