मान लीजिए, हमें 's' द्वारा दर्शाया गया एक उपस्ट्रिंग दिया गया है। हमें विशिष्ट उपस्ट्रिंग्स ढूंढनी हैं और इन उपस्ट्रिंग्स की संख्या को आउटपुट के रूप में वापस करना है।
इसलिए, यदि इनपुट है s = 'prrstvt', तो आउटपुट 26 होगा।
विशिष्ट उपस्ट्रिंग्स होंगी:
'pr', 'rrs', 'st', 'rr', 'tv', 'rstv', 'stvt', 'prrstv', 'prrstvt', 'rrstvt', 's', 'prrst', 'stv', 'rrstv', 'rst', 'v', 'tvt', 'rstvt', 'r', 'rs', 'vt', 't', 'prr', 'p', 'rrst', और 'prrs'।
इसे हल करने के लिए, हम निम्न चरणों का पालन करेंगे:
- visited := एक नया मैप
- s में प्रत्येक सूचकांक ind, और मान let के लिए, करें
- temp := एक नया सेट
- यदि ind-1 visited में मौजूद है, तो
- visited[ind-1] में प्रत्येक has_let के लिए, करें
- (has_let + let) को temp सूची में जोड़ें
- visited[ind-1] में प्रत्येक has_let के लिए, करें
- let को temp सूची में जोड़ें
- visited[ind] := temp
- res := एक नया सेट
- visited में प्रत्येक sets के लिए, करें
- visited[sets] को res में जोड़ें
- res का आकार वापस करें
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
def solve(s):
visited = dict()
for ind, let in enumerate(s):
temp = set()
if ind-1 in visited:
for has_let in visited[ind-1]:
temp.add(has_let+let)
temp.add(let)
visited[ind] = temp
res = set()
for sets in visited:
res.update(visited[sets])
return len(res)
print(solve('prrstvt'))
इनपुट
'prrstvt'
आउटपुट
26
