LeetCode-30. Substring with Concatenation of All Words

315 阅读4分钟

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…