30. Substring with Concatenation of All Words
- 刷题仓库地址
- 4. Median of Two Sorted Arrays
- 10. Regular Expression Matching
- 23. Merge k Sorted Lists
- 25. Reverse Nodes in k-Group
- 30. Substring with Concatenation of All Words
Description
You are given a string, s, and a list of words, words, that are all of the same length.
Find all starting indices of substring(s) in s that is a concatenation of each word in
words exactly once and without any intervening characters.
Example
1For example, given:
2s: "barfoothefoobarman"
3words: ["foo", "bar"]
4
5You should return the indices: [0,9].
6(order does not matter).
Translation
给你一个字符串s和一个长度相同的单词列表。从s中找出所有以单词列表串起来的子串的起始位置,这些字符串中的每个单词只是一个字符串,没有任何中介字符。
单词列表的串联顺序是任意的。意思就是找出s中恰好包含所有单词的子串的起始位置
Ideas
滑块、或者叫窗口搜索。大致意思是定义两个指针,start、end,我们的最终目的是希望,从start至end能恰好包含所有的单词,
即,所有单词可以串联成start至end的字符串。
初始化的时候start和end都是指向0,定义一个count,记录窗口(start,end)内的单词个数。
如果 end + word.length 没有超过 s.length,说明end后面还有可用的单词,然后开始循环
如果s的子串 [end,end+word.length),是一个单词,那么end移动到end+word.length,单词个数加1,
如果count与总的单词个数相等,说明找到一个答案。
如果s的子串 [end,end+word.length),不是一个单词,start后移,end = start,单词个数清零。
关于重复单词的问题:
定义两个map集合,一个用于记录原始的单词与个数的映射,一个用于记录滑块窗口的单词与个数的映射。
每次移动end的时候,判断一下滑块里的当前单词个数是否超出了原始的单词个数,超出就移动start,临时数据清零
Accept Code
1 public static List<Integer> findSubstring(String s, String[] words) {
2 Map<String, Integer> wordMap = new HashMap<>();
3 for (String word : words) {
4 if (wordMap.containsKey(word)) {
5 wordMap.put(word, wordMap.get(word) + 1);
6 } else {
7 wordMap.put(word, 1);
8 }
9 }
10
11 Map<String, Integer> temp = new HashMap<>();
12 List<Integer> ans = new ArrayList<>();
13 int start = 0;
14 int end = 0;
15 int wordLength = words[0].length();
16 int arrLength = words.length;
17 int tempArrLength = 0;
18 while (end + wordLength < s.length() + 1) {
19 String tempWord = s.substring(end, end + wordLength);
20
21 Integer value = wordMap.get(tempWord);
22 Integer tempValue = temp.get(tempWord);
23
24 if (value != null && (tempValue == null || tempValue < value)) {
25 if (tempValue == null) {
26 tempValue = 0;
27 }
28 temp.put(tempWord, tempValue + 1);
29 end += wordLength;
30 tempArrLength++;
31 } else {
32 start++;
33 end = start;
34 tempArrLength = 0;
35 temp.clear();
36 }
37 if (tempArrLength == arrLength) {
38 ans.add(start);
39 start++;
40 end = start;
41 tempArrLength = 0;
42 temp.clear();
43 }
44 }
45 return ans;
46
转载请注明出处
本文链接:zdran.com/20180331.ht…