Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

串联所有单词的子串

Posted on In , ,
Symbols count in article: 2.2k Reading time ≈ 2 mins.

来自Leetcode第30题串联所有单词的子串

给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中所有单词串联形成的子串的起始位置。

注意子串要与 words 中的单词完全匹配，中间不能有其他字符，但不需要考虑 words 中单词串联的顺序。

示例 1：

1
2
3
4
5
6
7
输入：
  s = "barfoothefoobarman",
  words = ["foo","bar"]
输出：[0,9]
解释：
从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
输出的顺序不重要, [9,0] 也是有效答案。

首先用一个HashMap存储words里的所有单词以及对应的频次，接着从字符串s的第一个字符开始遍历，按每次增加一个单词的长度（因为题目给定所有单词的长度是固定的），在外层循环里维护一个遍历count用来记录前进了多少个单词，以及一个子串map，用来记录子串里的单词。
当counts小于总的字符串数组长度时,依次读取单个单词长度len的字符串,如果全局map有这个单词,说明是子串之一,将其放入子串map,并比较子串map和全局map里的出现频率,如果超过了还要调整初始指针j的位置,并删除对应的子串map里的单词;如果遇到不存在的单词,就清空当前滑动窗口,指针前进.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> res = new ArrayList<>();
        if (s.length() == 0 || words.length == 0){
            return res;
        }
        int unit = words[0].length();  //每个单词的长度
        int allNums = words.length;  //所有单词的总共长度
        HashMap<String,Integer> allwords = new HashMap<>();
        for(String word : words){
            allwords.put(word,1+allwords.getOrDefault(word,0));
        }

        for(int i = 0 ; i < unit ; ++i){
            //按单单词遍历
            HashMap<String ,Integer> subMap = new HashMap<>();  //子串字典
            int counts = 0 ;  //计数一共前进了多少个单词
            for(int j = i ; j < s.length() - unit*allNums + 1 ; j += unit){
                //boolean hasRemoved = false;
                while (counts < allNums){
                    String curWord = s.substring(j + counts*unit, j + (counts+1)*unit);
                    if(allwords.containsKey(curWord)){
                        int freq = subMap.getOrDefault(curWord,0);
                        subMap.put(curWord,freq+1);
                        //如果出现的次数超过了，需要前进滑动窗口
                        if(subMap.get(curWord) > allwords.get(curWord)){
                            int cntRemoved = 0;
                            while (subMap.get(curWord) > allwords.get(curWord)){
                                String sub = s.substring(j+cntRemoved*unit,j+(cntRemoved+1)*unit);
                                int fre= subMap.get(sub);
                                if(fre > 1)
                                    subMap.put(sub,fre-1);
                                else
                                    subMap.remove(sub);
                                cntRemoved++;
                            }
                            counts = counts - cntRemoved + 1;  //计数减掉移动的窗口，然后还要算上当前单词
                            j = j + (cntRemoved - 1)*unit;  //减一是因为后面还要加1
                            break;
                        }
                    }else{
                        //此时单词不匹配
                        subMap.clear();  //直接清空滑动窗口
                        j = j + counts * unit;
                        counts = 0;
                        break;
                    }
                    counts++;
                }
                if(counts == allNums) {
                    res.add(j);
                    String first = s.substring(j,j+unit);  //移除子串最前面那个元素
                    int freq= subMap.get(first);
                    if(freq > 1)
                        subMap.put(first,freq-1);
                    else
                        subMap.remove(first);
                    counts--;
                }
            }
        }
        return res;
    }
}