-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathShortestSubSegment.py
53 lines (46 loc) · 1.3 KB
/
ShortestSubSegment.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
def func(atring, ip, allWordsDone):
count = 0
op_poss = []
wc = 0
for word in string.split(' '):
print (ip, all(ip.values()))
if all(ip.values()) == True:
for w in ip.keys():
ip[w] = False
break
if word in ip.keys() and allWordsDone == False and ip[word] == False:
op_poss.append(count)
ip[word] = True
count = count + 1
return op_poss
def getString(string, start, end):
count = 0
st = ""
for word in string.split(' '):
if start <= count and count <= end:
st = st + word + " "
count = count + 1
return st
string = "this is a test this is a programming test this is a programming test in any language"
# string = "this is the best problem i have ever solved"
ip = {"this":False, "a":False, "test":False, "programming":False}
# ip = {"this":False, "is":False, "best":False}
count = 0
op_poss = []
allWordsDone = False
wc = 0
for word in string.split(' '):
wc = wc + 1
mini = wc
op_s = ""
while (len(string.split(' ')) > len(ip)):
op_poss = func(string, ip, allWordsDone)
if len(op_poss) == len(ip):
if abs((op_poss[len(op_poss) - 1] - op_poss[0]) + 1) < mini:
mini = abs((op_poss[len(op_poss) - 1] - op_poss[0]) + 1)
op_s = getString(string, op_poss[0], op_poss[-1])
string = string[string.find(' ') + 1:]
if op_s is "":
print ("No Sub-Segment found")
else:
print (op_s)