समस्या विवरण
दो स्ट्रिंग्स word0, word1 और एक टेक्स्ट दिया गया है। हमें टेक्स्ट में word0 और word1 के किन्हीं दो ऑकरेंस के बीच न्यूनतम दूरी (शब्दों की संख्या में) ज्ञात करनी है। यदि दोनों शब्द टेक्स्ट में नहीं हैं तो -1 वापस करें।
उदाहरण
इनपुट: text = "cat dog abcd dog cat cat abcd dog wxyz", word0 = "abcd", word1 = "wxyz"
आउटपुट: 1 (क्योंकि "abcd" और "wxyz" के बीच एक शब्द "dog" है)
एल्गोरिदम
- टेक्स्ट को शब्दों की सूची
word_listमें विभाजित करें ans = len(word_list)(अधिकतम संभव दूरी) औरL = Noneइनिशियलाइज़ करें- प्रत्येक इंडेक्स
Rके लिए:- यदि
word_list[R]word0याword1है:- यदि
LNone नहीं है औरword_list[R] != word_list[L]:ans = min(ans, R - L - 1)अपडेट करें
L = Rअपडेट करें
- यदि
- यदि
ans अपरिवर्तित है तो -1 वापस करें, अन्यथा ansपायथन कार्यान्वयन
class Solution:
def solve(self, text, word0, word1):
word_list = text.split()
ans = len(word_list)
L = None
for R in range(len(word_list)):
if word_list[R] == word0 or word_list[R] == word1:
if L is not None and word_list[R] != word_list[L]:
ans = min(ans, R - L - 1)
L = R
return -1 if ans == len(word_list) else ans
ob = Solution()
text = "cat dog abcd dog cat cat abcd dog wxyz"
word0 = "abcd"
word1 = "wxyz"
print(ob.solve(text, word0, word1))
इनपुट
"cat dog abcd dog cat cat abcd dog wxyz", "abcd", "wxyz"
आउटपुट
1