正文
[leetcode] 30. 与所有单词相关联的字串（cn第653位做出此题的人~）
提示：扫一扫查出行【扫一扫了解最新限行尾号】
复制提示
30. 与所有单词相关联的字串
这个题做了大概两个小时左右把。。。严重怀疑leetcode的judge机器有问题。同样的代码交出来不同的运行时长，能不能A题还得看运气？
大致思路是，给words生成一关于s的字典，用来记录每个word在s中出现的 所有 位置，注意可能会出现相同的word。然后递归枚举words的排列情况，一一校验是否符合条件（即连在一起）。用到了递归+记忆化搜索+kmp+几个剪枝
一直最后几个测试用例上TLE，囧啊，甚至一度怀疑是不是还有更优的做法。
然后开始考虑剪枝：
- 记忆化搜索：即同一层下同样的word只搜一次就好。（又多过了几个测试样例）
- 使用kmp算法：一开始在生成字典时直接用的java String的indexOf，效率太低了，换用kmp后，又多过了两个，不过还是不够
- 在确定头位置时，如果此时s剩余长度根本不够words的所有长度，直接跳过 ，妈的，此时发现还有最后两个测试用例过不了。。。仔细研究了下数据，又搞出一个特判剪枝2333333333
- 当words只有两种时，即word1与word2，那么可以先验证下word1+word2或word2+word1是否是s子串，如果不是的话不用搜了，肯定搜不到答案。。。
class Solution {
class KMPStringMatcher {
/**
* 获取KMP算法中pattern字符串对应的next数组
*
* @param p 模式字符串对应的字符数组
* @return
*/
protected int[] getNext(char[] p) {
// 已知next[j] = k,利用递归的思想求出next[j+1]的值
// 如果已知next[j] = k,如何求出next[j+1]呢?具体算法如下:
// 1. 如果p[j] = p[k], 则next[j+1] = next[k] + 1;
// 2. 如果p[j] != p[k], 则令k=next[k],如果此时p[j]==p[k],则next[j+1]=k+1,
// 如果不相等,则继续递归前缀索引,令 k=next[k],继续判断,直至k=-1(即k=next[0])或者p[j]=p[k]为止
int pLen = p.length;
int[] next = new int[pLen];
int k = -1;
int j = 0;
next[0] = -1; // next数组中next[0]为-1
while (j < pLen - 1) {
if (k == -1 || p[j] == p[k]) {
k++;
j++;
next[j] = k;
} else {
k = next[k];
}
}
return next;
}
public int indexOf(String source, String pattern) {
int i = 0, j = 0;
char[] src = source.toCharArray();
char[] ptn = pattern.toCharArray();
int sLen = src.length;
int pLen = ptn.length;
int[] next = getNext(ptn);
while (i < sLen && j < pLen) {
// 如果j = -1,或者当前字符匹配成功(src[i] = ptn[j]),都让i++,j++
if (j == -1 || src[i] == ptn[j]) {
i++;
j++;
} else {
// 如果j!=-1且当前字符匹配失败,则令i不变,j=next[j],即让pattern模式串右移j-next[j]个单位
j = next[j];
}
}
if (j == pLen)
return i - j;
return -1;
}
}
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> ans = new ArrayList<>();
if (s.equals("")) {
return ans;
}
if (words.length == 0) {
return ans;
}
Map<String, List<Integer>> dic = new HashMap<>();
KMPStringMatcher kmpStringMatcher = new KMPStringMatcher();
for (String word : words) {
if (dic.containsKey(word)) {
// word 可能出现重复的
continue;
}
int k = 0, p = 0;
int tmp = 0;
while ((tmp = kmpStringMatcher.indexOf(s.substring(p), word)) != -1) {
k = p + tmp;
dic.computeIfAbsent(word, x -> new ArrayList<Integer>()).add(k);
p = k + 1;
}
}
Set<String> keys = dic.keySet();
if (keys.size() == 2) {
Iterator<String> iterator = keys.iterator();
String tmp1 = iterator.next();
String tmp2 = iterator.next();
if (kmpStringMatcher.indexOf(s, tmp1 + tmp2) == -1 && kmpStringMatcher.indexOf(s, tmp2 + tmp1) == -1) {
return new ArrayList<>();
}
}
Map<String, Integer> flagMap = new HashMap<>();
List<String> standBy = new ArrayList<>(Arrays.asList(words));
for (String s1 : standBy) {
if (!dic.containsKey(s1)) break;
//记忆化搜索剪枝：同一层下同样的word没必要继续搜下去
if (flagMap.containsKey(s1)) continue;
flagMap.put(s1, 1);
List<String> tmpStandBy = new ArrayList<>(standBy);
tmpStandBy.remove(s1);
for (Integer p : dic.get(s1)) {
// 剪枝，如果字串长度根本不够匹配的，直接跳过
if (s.length() - (p + s1.length()) < tmpStandBy.size() * s1.length()) continue;
dfs(dic, tmpStandBy, p, p + s1.length(), s1.length(), ans);
}
}
// return ans.stream().distinct().collect(Collectors.toList());
return ans;
}
// p 当前子串的头位置，now表示当前子串的尾位置
public boolean dfs(Map<String, List<Integer>> dic, List<String> standby, int p, int now, int len, List<Integer> ans) {
if (standby.size() == 0) {
ans.add(p);
return true;
}
Map<String, Integer> flagMap = new HashMap<>();
for (String s1 : standby) {
if (!dic.containsKey(s1)) break;
//记忆化搜索剪枝：同一层下同样的word没必要继续搜下去
if (flagMap.containsKey(s1)) continue;
flagMap.put(s1, 1);
boolean flag = false;
for (Integer position : dic.get(s1)) {
if (position == now) {
flag = true;
break;
}
}
if (flag) {
List<String> tmpStandBy = new ArrayList<>(standby);
tmpStandBy.remove(s1);
if (dfs(dic, tmpStandBy, p, now + len, len, ans)) {
return true;
}
}
}
return false;
}
}
另外，看别人题解貌似可以用 滑动窗口 的思路来做，回头研究下
