LeetCode Problem 30 Substring with Concatenation of All Words (Java)

Source url:https://leetcode.com/problems/substring-with-concatenation-of-all-words/

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

Example 1:

Input: s = “barfoothefoobarman”, words = [“foo”,”bar”]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are “barfoor” and “foobar” respectively. The output order does not matter, returning [9,0] is fine too.

First, this kind of substring must is anagrams of words too. So you can use function findAnagrams of problem 438 first.

Then we check in the returned list to make sure each word in words exactly once and without any intervening characters.

This is the code:

Running time is 94ms.

Code download address: https://github.com/tinyfool/leetcode/tree/master/src/p0030

Want to know details of the sliding window algorithm, check my post: The Sliding Window Algorithm for string and array.

Leave a Reply

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.