与所有单词相关联的字串
给定一个字符串 s 和一些长度相同的单词 words。在 s 中找出可以恰好串联 words 中所有单词的子串的起始位置。
注意子串要与 words 中的单词完全匹配,中间不能有其他字符,但不需要考虑 words 中单词串联的顺序。
示例 1:
输入:
s = "barfoothefoobarman",
words = ["foo","bar"]
输出: [0,9]
解释: 从索引 0 和 9 开始的子串分别是 "barfoor" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。
题目的意思是给你一个字符串,和一个字符串的数组,需要返回一个该字符串的索引组成的数组,返回的索引有如下性质:从每个索引开始,长度为L的字串需要精确包含字符串数组中的所有字符串(不多不少)。L 为字符串数组中所有字符串长度之和。
解决思路,使用一个map,键为字符串数组中的字符串,值为该字符串在字符串数组中出现的次数。遍历字符串s,寻找和字符串数组中的字符串相同的字串,找到后map中的值减一,否则重新初始化map,从下一个字符开始遍历。如果map中所有的值都为0,则找到了一个符合条件的子串,索引压入数组。
1 import java.util.ArrayList; 2 import java.util.HashMap; 3 import java.util.List; 4 5 class Solution { 6 public static void initializeMap(HashMaphashMap, String[] words){ 7 //hashMap=new HashMap (); 8 for(int i=0;i findSubstring(String s, String[] words) {17 if(s==null || s.equals("") || words.length==0) return new ArrayList ();18 HashMap hashMap=new HashMap ();19 int singleWordLen=words[0].length();//单个字串长度20 int wordsLen=words.length;21 int slen=s.length();22 int i,j,count;23 boolean countChange=false;//判断是否改变过map中的值,如果没有变则无需重新初始化24 List result=new ArrayList ();25 count=wordsLen;//计数器表示还需要找到的字串个数26 if(wordsLen==0 || slen==0) return result;27 initializeMap(hashMap,words);28 for(i=0;i<=slen-wordsLen*singleWordLen;i++){29 String subStr=s.substring(i,i+singleWordLen);30 j=i;31 //当该字串存在于map中且值大于0,并且j不越界的情况下32 while(hashMap.containsKey(subStr) && hashMap.get(subStr)!=0 && j+singleWordLen<=slen){33 hashMap.put(subStr,hashMap.get(subStr)-1);34 count--;35 countChange=true;//改变了map的值36 j=j+singleWordLen;37 if(j+singleWordLen<=slen)38 subStr=s.substring(j,j+singleWordLen);//下一个字符串39 else40 break;41 if(!hashMap.containsKey(subStr))42 break;43 }44 if(count==0){45 result.add(i);//找齐所有字符串数组中的字串后把该索引压入46 }47 if(countChange){48 hashMap.clear();49 initializeMap(hashMap,words);50 count=wordsLen;51 countChange=false;52 }53 }54 return result;55 }56 57 public static void main(String[] args){58 String s="wordgoodgoodgoodbestword";59 String[] words={"word","good","best","good"};60 List list=findSubstring(s,words);61 for(int i:list){62 System.out.println(i);63 }64 }65 }