转载

LeetCode 第30题 Substring with Concatenation of All Words【滑动窗口】(Java)

原题地址为: https://leetcode.com/problems/substring-with-concatenation-of-all-words/

要求

给定字符串s,和有一个单词列表words,每个词长度相等。在s中寻找,包含全部词,且每个词只出现一次,没有任何多余其他字符的子串。

例 1:

输入:

s = “barfoothefoobarman”,

words = [“foo”,”bar”]

输出:  [0,9]

0,9分别对应了”barfoor”和”foobar”

例 2:

输入:

s = “wordgoodgoodgoodbestword”,

words = [“word”,”good”,”best”,”word”]

输出: []

我的解题思路是这样的,首先这样的子串,一定也是words里面单词练在一起的某个组合。那么我们可以先调用438题目的函数findAnagrams。这样就大大减少了选项。

然后,我们从返回的list去检查,每一个子串,是否包含了words里面的单词,所以代码也不复杂。

不包含findAnagrams实现的话,包含两个函数,一个是checkwords,看看一个子串是否包含words里面的单词。另外一个函数是结果函数 findSubstring。

LeetCode 第30题 Substring with Concatenation of All Words【滑动窗口】(Java)
LeetCode 第30题 Substring with Concatenation of All Words【滑动窗口】(Java)

这个做起来简单,但是性能一般,执行需要94ms。问题应该出在checkwords的实现,不过我暂时懒得优化了,毕竟这次主要目的是练习滑动窗口的技巧。

本题代码地址为: https://github.com/tinyfool/leetcode/tree/master/src/p0030

本文假设你对滑动窗口概念有所了解,如果你对滑动窗口的概念不够了解,请参看我介绍 滑动窗口的文章,里面有详细的解释 。

原文  http://codechina.org/2019/05/leetcode-第30题-substring-with-concatenation-of-all-words【滑动窗口】(java)/
正文到此结束
Loading...