乘风破浪：LeetCode真题_030_Substring with Concatenation of All Words
一、前言
这次我们还是找字符串的索引，不过，需要将另一个字符串列表中的字符串拼接起来，要求全部都拼接并且出现且仅出现一次，然后在字符串中求子串的起始位置。
二、Substring with Concatenation of All Words
2.1 问题
2.2 分析与解决
其实我们仔细想一下，求子串的索引可以使用工具库来解决，重要的是将字符串列表中的字符串进行组合，假设一共N个字符串，那么有N*(N-1)*...*(1)中组合方式，但是还要考虑到重复的问题，然后求子串即可。这让我们想到了是否可以使用递归来进行组合，这一点是可以的，于是我们在不考虑重复的情况下可以得到解答，就算重复了，最后去除重复的起始点只保留一个即可。这是一种笨办法。
当然我们还有其他的解法，我们可以通过HashMap的特性，将列表放入其中，然后从字符串s进行遍历，同样的将s进行剪裁和封装，然后进行比较，如果相等则记录索引，就这样遍历完s就可以得到结果了。
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res = new LinkedList<>();
if(s.length()==0 || words.length==0)
return new ArrayList<>();
HashMap<String,Integer> hs = new HashMap<>();
for (String w:words)
hs.put(w,hs.getOrDefault(w,0)+1);
int wl = words[0].length();
int wLen = words.length*words[0].length();
for (int i = 0 ; i +wLen<=s.length();i++)
{
String curS = s.substring(i,i+wLen);
HashMap<String,Integer> h = new HashMap<>();
for (int j = 0 ; j <curS.length();j+=wl)
h.put(curS.substring(j,j+wl),h.getOrDefault(curS.substring(j,j+wl),0)+1);
if (h.equals(hs))
res.add(i);
}
return res;
}
}
三、总结
通过java的一些特性，我们更快的求得了结果。