Python program to find the substring with concatenation of all words

Question

This is a Leetcode problem:

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

Here is my solution to the problem:

class Solution:
 def __init__(self, S, L):
 self.S = S
 self.L = L
 def findSubstring(self, S, L): 
 res = [] # result list
 num = len(L) # length of the str list 
 ls = len(S)
 if num == 0:
 return []
 str_len = len(L[0]) # length of each str
 #creating the map: counting the occurrence of each string
 map_str = dict((x,L.count(x)) for x in set(L))
 i = 0
 while i + num * str_len - 1 < ls:
 map_str2 = {}
 j = 0
 while j < num:
 subs = S[i + j * str_len:i + j * str_len + str_len ]
 if not subs in map_str:
 break
 else:
 map_str2[subs] = map_str2.get(subs, 0) + 1
 if map_str2[subs]>map_str[subs]:
 break
 j = j + 1
 if j == num:
 res.append(i)
 i = i + 1
 return res
S = "barfoothefoobarman"
L = ["bar","foo"]
index = Solution(S, L)
print(index.findSubstring(S, L))

Here are some example inputs/outputs:

S = "barfoothefoobarman"
L = ["bar", "foo"]
>>> [0, 9]
-------------------------------------------------------------------
S = "lingmindraboofooowingdingbarrwingmonkeypoundcake"
L = ["fooo", "barr", "wing", "ding", "wing"]
>>> [13]

So I would like to know whether I could make this program shorter and more efficient.

Any help would be highly appreciated.

Answer 1

As I told in another answers, your code is very C/C++ styled, it is not Pythonic. Try to avoid manual iteration with indices as much as possible. Python has an enormous standard library that contains many useful modules. I already recommended you an itertools module. It contains pair of dozens generic functions to work with iterators. One of them - permutations - do 90% of your work:

Return successive r length permutations of elements in the iterable.

permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC

permutations(range(3)) --> 012 021 102 120 201 210

For list L, it returns all possible permutations iterator. If we will join each permutation, we will get the needed search substring.

But next we will have a problem. Python has no built-in function or easy method to find indices of all found substrings in the string (it is strange, I hope they will add it to future Python versions). So you have to do it manually. You can run string.find(substring) in the loop and, after each found substring, to shorten the search range.

Here is the code for my solution:

from itertools import permutations
class Solution(object):
 """
 Leetcode-XXXXX solution
 """
 def find_chained_substrings(self, S, L):
 result = []
 for perm in permutations(L):
 chained_string = ''.join(perm)
 i = S.find(chained_string)
 while i != -1:
 result.append((i, perm))
 i = S[i+len(chained_string):].find(chained_string)
 return result
 
waka = 'foobarwakatttpingpong-ongpingpt'
lst = ['foo', 'bar', 'waka']
lst2 = ['t', 'pingp', 'ong']
S = Solution()
S.find_chained_substrings(waka, lst2)

It will return:

[(12, ('t', 'pingp', 'ong')), (22, ('ong', 'pingp', 't'))]

Note, that your Leetcode task needs only indices. I construct index-substring tuple for readability and simplier testing. If you want to make a Leetcode solution, replace this string:

result.append((i, perm))

with this:

result.append(i)

---

P.S. I strongly recommend you to read the Python Standard Library documentation. It will greatly improve your Python programming skill and will shift you from the C/C++ish style to Pythonic style.