Substring with Concatenation of All Words – LeetCode

by

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

Substring with Concatenation of All Words

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:

class Solution(object):
    def findSubstring(self, s, words):
        """
        :type s: str
        :type words: List[str]
        :rtype: List[int]
        """
        dict = collections.defaultdict(int)
        for w in words:
            dict[w] += 1
        l, res = len(words[0]), []
        for i in xrange(l):
            dict1 = dict.copy()
            j = i
            while j < len(s) - l + 1:
                dict1[s[j : j + l]] -= 1
                while dict1[s[j : j + l]] < 0:
                    dict1[s[i : i + l]] += 1
                    i += l
                j += l
                if (j - i) / l == len(words):
                    res.append(i)
        return res

READ MORE

Python-related posts Visit HERE

C++ related posts Visit HERE

Databases related posts Visit HERE

Data Structures related posts visit HERE

Algorithms related posts visit HERE

Data Science related posts visit HERE