Substring with Concatenation of All Words

题意:给定一个字符串s和一组单词,每个单词长度一致,这些单词可以组成一个字符串称为concatenated substring,找出s中所有这些字符串的开始下标。

30. Substring with Concatenation of All Words (opens new window)

# 解法 1:哈希表

建立一个hashmap词典,key是string,value是integer,表示某个单词出现的次数。遍历字符串s,如果遇到词典中的单词则减一,直到全部减到0,表示存在一个符合要求的子串。

设a=单词数量,b=单词长度,n=字符串s的长度。

时间复杂度O(a+nab),空间复杂度O(a+b)。

class Solution {

    private HashMap<String, Integer> wordMap = new HashMap<>();
    private int substringLength;
    private int wordCount;
    private int wordLength;

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> indexes = new ArrayList<>();
        wordCount = words.length;
        wordLength = words[0].length();
        substringLength = wordCount * wordLength;
        for (int i = 0; i < wordCount; i++) {
            wordMap.put(words[i], wordMap.getOrDefault(words[i], 0) + 1);
        }
        int fullLength = s.length();
        // 遍历字符串找出所有可能的子串
        for (int i = 0; i < fullLength + 1 - substringLength; i++) {
            if (canfindSubstring(s, i)) {
                indexes.add(i);
            }
        }
        return indexes;
    }

    private boolean canfindSubstring(String s, int index) {
        // 新建一个词典
        HashMap<String, Integer> map = new HashMap<>(wordMap);
        int wordsUsed = 0;
        for (int i = index; i < index + substringLength; i+= wordLength) {
            String word = s.substring(i, i + wordLength);
            // 统计词典中单词出现的次数,遇到则减一
            int remain = map.getOrDefault(word, 0);
            if (remain > 0) {
                wordsUsed++;
                map.put(word, remain - 1);
            } else {
                break;
            }
        }
        return wordsUsed == wordCount;
    }
}

# 解法 2:滑动窗口

在上一个解法中在遍历过程中存在着大量重复计算,因此效率较低。处理字符串遍历问题时,可以使用滑动窗口加速。

左右指针从最左边开始,之前遍历时移动数是1,其实词典里的单词长度一致,可以改为和单词长度相同。

先移动右指针,如果单词不在词典里,那么在接下来的范围里是不可能找到子串的,所以可以移动左指针,跳过这个单词,重置窗口。如果单词在词典里,记录下这个单词的出现次数和总单词数。当次数到达词典里的单词次数时且没有重复单词出现时,记录左指针的下标。当出现重复单词时,移动右指针已没有意义,需要移动左指针,直到把重复单词删除。当左右指针宽度到达窗口宽度,也需要移动左指针。移动左指针后,需要判断最左边去掉的单词是否是重复的,该单词出现次数减一后和词典中的单词次数比较,如果小于说明是必要的,总单词数减一,否则说明是重复单词,去掉后窗口内就没有重复单词了。

因为下标跳跃改为单词长度,可能出现xfoobar[foo,bar]这种情况,所以需要在滑动窗口外层再包一层循环。

设a=单词数量,b=单词长度,n=字符串s的长度。

空间复杂度O(a+b),时间复杂度O(a+b*n)。

l = 左指针,r = 右指针

不存在单词
foobarthefoobar => foobarthefoobar
   |  |                     |
   l  r                     l
                            r

重复单词和到达窗口宽度
foobarbarfoo => foobarbarfoo
   |     |            |  |
   l     r            l  r
class Solution {
    private HashMap<String, Integer> wordMap = new HashMap<>();
    private int wordLength;
    private int wordCount;
    private int sLength;
    private int substringLength;

    public List<Integer> findSubstring(String s, String[] words) {
        List<Integer> indexes = new ArrayList<>();
        wordLength = words[0].length();
        wordCount = words.length;
        sLength = s.length();
        substringLength = wordLength * wordCount;
        for (int i = 0; i < wordCount; i++) {
            wordMap.put(words[i], wordMap.getOrDefault(words[i], 0) + 1);
        }
        for (int i = 0; i < wordLength; i++) {
            HashMap<String, Integer> wordsFound = new HashMap<>();
            int wordsUsed = 0;
            boolean isExcessWord = false;
            int left = i;
            for (int right = left; right < sLength + 1 - wordLength; right += wordLength) {
                String word = s.substring(right, right + wordLength);
                if (!wordMap.containsKey(word)) {
                    wordsFound.clear();
                    wordsUsed = 0;
                    isExcessWord = false;
                    left = right + wordLength;
                } else {
                    while (right - left == substringLength || isExcessWord) {
                        String leftWord = s.substring(left, left + wordLength);
                        left += wordLength;
                        wordsFound.put(leftWord, wordsFound.get(leftWord) - 1);
                        if (wordsFound.get(leftWord) >= wordMap.get(leftWord)) {
                            isExcessWord = false;
                        } else {
                            wordsUsed--;
                        }
                    }
                    wordsFound.put(word, wordsFound.getOrDefault(word, 0) + 1);
                    if (wordsFound.get(word) <= wordMap.get(word)) {
                        wordsUsed++;
                    } else {
                        isExcessWord = true;
                    }
                    if (wordsUsed == wordCount && !isExcessWord) {
                        indexes.add(left);
                    }
                }
            }
        }
        return indexes;
    }
}