leetcode 30 Substring with Concatenation of All Words

You are given a string, S, and a list of words, L, that are all of the same length. Find all starting indices of substring(s) in S that is a concatenation of each word in L exactly once and without any intervening characters.

For example, given:
S: "barfoothefoobarman"
L: ["foo", "bar"]

You should return the indices: [0,9].
(order does not matter).

题目地址:leetcode Substring with Concatenation of All Words

题目大意:给定一些单词words(可能重复,长度相同)和一个长字符串s,要求求出长字符串的所有起始位置,使得给定的所有单词在之后出现一次且仅一次

思路:

方法一

首先用对words中每个单词进行计数count_word(hash表),

枚举起始位置和终点位置,每次用cur_cnt计数,若单词存在且cur_cnt[word] <= count_word[word],总计数total_in+1, 如果rotal_in等于words的长度,放入答案ans

复杂度O(len(s) * len(words) * t), t为计算每个单词hash值的时间。

C++ 125ms

Python

 

方法二

我们可以用滑动窗口思想优化上面的过程。

设word_len为单词的长度,枚举可能的起点为[0, word_len],

然后枚举s中的单词,令start = i表示当前窗口的起点,令j = i表示当前枚举的字符串s的起点,每次枚举结束j+= word_len

在枚举s中单词的过程中保持一个合法的窗口 使得cur_cnt[word] <= count_word[word],若窗口不合法,则说明之前已经有单词存在,不断的令start对应的单词-=1,start+=word_len即可。

复杂度O(word_len * len(s) / word_len * 2)= O(len(s) * 2),乘上2是因为一次遍历中,每个单词最多两次。(PS:这个复杂度没有计算哈希的代价,假设为O(1))

C++

Python

 

更多题解可以查看: https://www.hrwhisper.me/leetcode-algorithm-solution/

本博客若无特殊说明则由 hrwhisper 原创发布
转载请点名出处:细语呢喃 > leetcode 30 Substring with Concatenation of All Words
本文地址:https://www.hrwhisper.me/leetcode-substring-with-concatenation-of-all-words/

打赏一杯咖啡钱呗

Leetcode , . permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *