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。

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

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

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

打赏

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据