首页 > 代码库 > Leetcode30--->Substring with Concatenation of All Words(主串中找出连接给定所有单词的子串的位置)
Leetcode30--->Substring with Concatenation of All Words(主串中找出连接给定所有单词的子串的位置)
题目：给定一个字符串S（主串），一个字符串数组words,其中的字符串的长度相同。找到所有的子串位置，要求是words中字符串的一个连接，而且没有交叉；
举例：
For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]
You should return the indices: [0,9].
解题思路：
1. 采用窗口机制，假设此时每个单词的长度为wordlen;
2. 先将words中的单词存储在hashmap中，key为单词，value为单词出现的次数；
3. 在S中以单词长遍历每个单词，看其在hashmap中是否出现，若出现，则窗口的左边界即可确定，然后依次向后遍历，若其中有单词不出现在hashmap中，则直接看下一个单词，窗口的左边界也会更新。若从窗口的左边界遍历找到了与words中单词相拼接的字符串，则将左窗口位置加入到结果集中，左窗口移向下一个单词。
代码如下：
1 public class Solution { 2 public List<Integer> findSubstring(String s, String[] words) { 3 List<Integer> list = new ArrayList<Integer>(); 4 if(s == null || words == null || s.length() < 1 || words.length < 1) 5 return list; 6 HashMap<String, Integer> hm = new HashMap<String, Integer>(); 7 for(int i = 0, len = words.length; i < len; i++) // 将数组中的单词放入到hashmap中，由于数组中有可能有多个相同的单词，所以还需要计数 8 { 9 if(hm.containsKey(words[i]))10 hm.put(words[i], hm.get(words[i]) + 1);11 else12 hm.put(words[i], 1);13 }14 int wordlen = words[0].length(); // 单词的长度15 int strlen = words.length; // 单词所组成串的长度16 int i = 0; // 循环的次数17 int len = s.length();18 while(i < wordlen)19 {20 int left = i; // 窗口的左边界21 int count = 0; // 匹配了hm中的单词数目22 HashMap<String, Integer> curr = new HashMap<String, Integer>(); // 记录窗口中已经匹配的单词及其出现的次数23 for(int j = i; j <= len - wordlen; j = j + wordlen)24 {25 String str = s.substring(j, j + wordlen); // 取一个单词26 if(hm.containsKey(str)) // 如果字典中包含该单词27 {28 if(curr.containsKey(str)) // 将单词加入到当前遍历的字典中29 curr.put(str, curr.get(str) + 1);30 else31 curr.put(str, 1);32 if(hm.get(str) >= curr.get(str)) // str在主串中出现的次数不能小于当前窗口的str出现的次数，否则窗口就要缩小33 count ++;34 else35 {36 while(hm.get(str) < curr.get(str)) // 如果当前窗口的单词出现次数大于给定的数组中的单词次数,窗口需要缩小37 {38 String temp = s.substring(left, left + wordlen);39 if(curr.containsKey(temp))40 {41 curr.put(temp, curr.get(temp) - 1);42 if(curr.get(temp) < hm.get(temp))43 count--;44 }45 left += wordlen;46 }47 }48 if(count == strlen) // 如果此时curr中所保存的单词数量与给定的words中的单词数目是一样的，则将当前窗口的左边缘加入结果49 {50 list.add(left);51 String ss = s.substring(left, left + wordlen);52 if(curr.containsKey(ss))53 {54 curr.put(ss, curr.get(ss) - 1);55 count -- ;56 }57 left += wordlen;58 }59 }60 else // 如果字典中不包含该单词，则直接看下一个单词61 {62 left = j + wordlen;63 count = 0;64 curr.clear();65 }66 }67 i ++;68 }69 return list;70 }71 }
Leetcode30--->Substring with Concatenation of All Words(主串中找出连接给定所有单词的子串的位置)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。