Substring with Concatenation of All Words - LeetCode
YTTMP3
Posted on February 6, 2022
LeetCode has a hard coding Problem in Its' Algorithm Section "Substring with Concatenation of All Words". Today We are going to solve this problem. LeetCode Link of the Problem is HERE
Question
You are given a string s and an array of strings words of the same length. Return all starting indices of substring(s) in s that is a concatenation of each word in words exactly once, in any order, and without any intervening characters.
You can return the answer in any order.
Examples
Input: s = "barfoothefoobarman", words = ["foo","bar"]
Output: [0,9]
Explanation: Substrings starting at index 0 and 9 are "barfoo" and "foobar" respectively.
The output order does not matter, returning [9,0] is fine too.
Input: s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
Output: []
Input: s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
Output: [6,9,12]
Constraints:
1 <= s.length <= 104
s consists of lower-case English letters.
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] consists of lower-case English letters.
Solution to Substring with Concatenation of All Words
The Skeleton code given by LeetCode is
class Solution(object):
def findSubstring(self, s, words):
"""
:type s: str
:type words: List[str]
:rtype: List[int]
"""
So, for this question, my current proposal is to cut a substring of the corresponding length (the sum of the lengths of each element in words) from s and then trim this substring according to the length of a single word in words. A list is formed by smaller substrings. To determine if the sorted results of words and lists are the same, compare them. If that's the case, we'll go back to the beginning. Otherwise, keep going.
Complete Solution:
Complete Solution is available here
https://hecodesit.com/substring-with-concatenation-of-all-words-leetcode/
Posted on February 6, 2022
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.