![\\\"Leetcode:](\\\"/uploads/20241012/1728725766670a43066126e.jpg\\\")
समय जटिलता: सबसे खराब स्थिति में हम न्यूनतम(str1,str2) पर पुनरावृत्ति करते हैं और हमें str1 और str2 को फिर से बनाने की आवश्यकता होती है ताकि यह (str1.length str2.length) हो, इसलिए समग्र समय जटिलता होगी O(min(str1,str2) * (str1.length str2.length))
होगाअंतरिक्ष जटिलता: O(1) क्योंकि हमें किसी अतिरिक्त स्थान की आवश्यकता नहीं है।
","image":"http://www.luping.net/uploads/20241012/1728725766670a43065f5b5.jpg","datePublished":"2024-11-07T22:30:30+08:00","dateModified":"2024-11-07T22:30:30+08:00","author":{"@type":"Person","name":"luping.net","url":"https://www.luping.net/articlelist/0_1.html"}}
ब्राउज़ करें:221
दो स्ट्रिंग्स s और t के लिए, हम कहते हैं "t विभाजित करता है" यदि और केवल यदि s = t t t ... t t (यानी, t एक या अधिक बार स्वयं के साथ संयोजित होता है)।
दो स्ट्रिंग str1 और str2 दिए हुए, सबसे बड़ी स्ट्रिंग x लौटाएं जैसे कि x str1 और str2 दोनों को विभाजित करता है।
हालांकि लेटकोड ने इसे एक आसान समस्या के रूप में चिह्नित किया है, मुझे यह स्वीकार करना होगा कि मुझे तुरंत समाधान निकालना मुश्किल लगा।
मुझे लेटकोड द्वारा प्रदान किए गए परीक्षण मामलों की समीक्षा करने दें और अपनी उलझन को समझाने के लिए उन पर गौर करें।
इनपुट: str1 = "एबीसीएबीसी", str2 = "एबीसी"
आउटपुट: "एबीसी"इनपुट: str1 = "ABABAB", str2 = "ABAB"
आउटपुट: "एबी"
समस्या कथन और परीक्षण केस 1 से, मैंने यह निर्धारित किया कि हमें सबसे बड़ी स्ट्रिंग ("एबीसी") को आउटपुट करने की आवश्यकता है, जिसे संयोजित करके हम दोनों स्ट्रिंग प्राप्त कर सकते हैं। (डिफ़ॉल्ट स्ट्रिंग "एबीसी" === str2 और "एबीसी" "एबीसी" === str1)।
हालांकि, टेस्ट केस 2 को देखते हुए मुझे तुरंत एहसास हुआ कि मेरी समझ सही नहीं थी क्योंकि उसके अनुसार मुझे "एबीएबी" आउटपुट देना चाहिए क्योंकि यह सबसे लंबी स्ट्रिंग है जिसका उपयोग करके मैं दोनों स्ट्रिंग बना सकता हूं। लेकिन मैंने कोड करना शुरू कर दिया और समाधान निकालना शुरू कर दिया। (नौसिखिया गलती?)
मैं केवल एक समाधान निकालने में सक्षम था जहां:
जैसा कि आप देख सकते हैं कि मेरा समाधान उन स्ट्रिंग्स के लिए विफल रहा जहां str1 में str2 है लेकिन कुछ अन्य अतिरिक्त वर्ण भी हैं। उस आवश्यकता का उल्लंघन करना जो s = t t ... t t है।
मुझे मदद के लिए नीटकोड के समाधान की ओर रुख करना पड़ा। मैं जल्दी ही अपने मुद्दों को समझ गया:
मैं स्ट्रिंग की लंबाई का जीसीडी ढूंढ रहा था, स्ट्रिंग का नहीं। मुझे एक स्ट्रिंग ढूंढने की ज़रूरत है जहां उन स्ट्रिंग्स को दोहराते हुए मैं बिना किसी शेष अक्षर के दोनों स्ट्रिंग्स बना सकता हूं।
मुझे एहसास हुआ कि "एबीएबी" टेस्ट केस 2 का उत्तर क्यों नहीं हो सकता:
हमें x को इस प्रकार खोजना होगा कि यह दोनों स्ट्रिंग को समान रूप से विभाजित करे। इसलिए "ABAB" को स्ट्रिंग के रूप में लेते हुए आप पूरी तरह से str2 बना सकते हैं लेकिन str1 के लिए आप "ABABABAB" पर समाप्त होते हैं। आप 2 अतिरिक्त "एबी" के साथ समाप्त होते हैं और यह नहीं कह सकते कि आपने x को मिलाकर पूरी तरह से str1 बनाया है।
"ABAB" लंबाई 4 और "ABABAB" लंबाई 6। 2 स्ट्रिंग्स की GCD = 2। इसलिए आउटपुट को लंबाई 2 की एक स्ट्रिंग की आवश्यकता है।
समय जटिलता: सबसे खराब स्थिति में हम न्यूनतम(str1,str2) पर पुनरावृत्ति करते हैं और हमें str1 और str2 को फिर से बनाने की आवश्यकता होती है ताकि यह (str1.length str2.length) हो, इसलिए समग्र समय जटिलता होगी O(min(str1,str2) * (str1.length str2.length))
होगाअंतरिक्ष जटिलता: O(1) क्योंकि हमें किसी अतिरिक्त स्थान की आवश्यकता नहीं है।
अस्वीकरण: उपलब्ध कराए गए सभी संसाधन आंशिक रूप से इंटरनेट से हैं। यदि आपके कॉपीराइट या अन्य अधिकारों और हितों का कोई उल्लंघन होता है, तो कृपया विस्तृत कारण बताएं और कॉपीराइट या अधिकारों और हितों का प्रमाण प्रदान करें और फिर इसे ईमेल पर भेजें: [email protected] हम इसे आपके लिए यथाशीघ्र संभालेंगे।
Copyright© 2022 湘ICP备2022001581号-3
