
给定一个字符串 s 和一些长度相同的单词 words,找出 s 与 words 中所有单词(words 每个单词只出现一次)串联一起(words中组成串联串的单词的顺序随意)的字符串匹配的所有起始索引,子串要与串联串完全匹配,中间不能有其他字符。
举个例子,给定:
s:"barfoothefoobarman"
words:["foo", "bar"]
你应该返回的索引: [0,9]。(任意顺序)
详见:https://leetcode.com/problems/substring-with-concatenation-of-all-words/description/
Java实现:
class Solution {
public List<Integer> findSubstring(String s, String[] words) {
List<Integer> res=new ArrayList<Integer>();
if(s.isEmpty()||s==null||words==null||words.length==0){
return res;
}
int n=words.length;
int m=words[0].length();
Map<String,Integer> m1=new HashMap<String,Integer>();
for(String str:words){
if(m1.containsKey(str)){
m1.put(str,m1.get(str)+1);
}else{
m1.put(str,1);
}
}
for(int i=0;i<=s.length()-n*m;++i){
Map<String,Integer> m2=new HashMap<String,Integer>();
int j=0;
for(;j<n;++j){
String t=s.substring(i+j*m,i+j*m+m);
if(!m1.containsKey(t)){
break;
}
if(m2.containsKey(t)){
m2.put(t,m2.get(t)+1);
}else{
m2.put(t,1);
}
if(m2.get(t)>m1.get(t)){
break;
}
}
if(j==n){
res.add(i);
}
}
return res;
}
}
参考:https://www.cnblogs.com/grandyang/p/4521224.html
https://blog.csdn.net/fly_yr/article/details/47957459