Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> Python

Python में सबसे लंबा वैध पैरेंथेसिस


मान लीजिए हमारे पास एक स्ट्रिंग है, जिसमें खुलने और बंद होने वाले पैरेंथेसिस हैं। हमें वैध (वेल-फॉर्म्ड) पैरेंथेसिस की सबसे लंबी लंबाई ढूंढनी है। इसलिए यदि इनपुट "))(())())" जैसा है, तो परिणाम 6 होगा, क्योंकि वैध स्ट्रिंग "(())()" है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे −

  • एक स्टैक बनाएं, और -1 डालें, ans := 0 सेट करें

  • i के लिए range 0 से स्टैक की लंबाई - 1 तक

    • यदि s[i] खुलने वाला पैरेंथेसिस है, तो i को स्टैक में डालें

    • अन्यथा

      • यदि स्टैक खाली नहीं है और स्टैक का शीर्ष -1 नहीं है और s[स्टैक शीर्ष] खुलने वाला पैरेंथेसिस है, तो

        • स्टैक से शीर्ष तत्व हटाएं

        • ans := ans और i - स्टैक शीर्ष का अधिकतम

      • अन्यथा i को स्टैक में डालें

  • ans लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें −

class Solution(object): def longestValidParentheses(self, s): stack = [-1] ans = 0 for i in range(len(s)): if s[i] == "(": stack.append(i) else: if stack and stack[-1]!=-1 and s[stack[-1]] == "(": stack.pop() ans = max(ans,i - stack[-1]) else: stack.append(i) return ans ob = Solution() print(ob.longestValidParentheses("))(())())"))

इनपुट

"))(())())"

आउटपुट

6

  1. - पायथन में मिन स्टैक

    यहां हम देखेंगे कि कैसे एक स्टैक बनाया जाए जो पुश, पॉप, टॉप, और न्यूनतम तत्व को स्थिर समय में प्राप्त कर सके। फंक्शन होंगे push(x), pop(), top() और getMin()। हल करने के चरण स्टैक को अनंत के रूप में न्यूनतम तत्व से आरंभ करें पुश ऑपरेशन push(x) के लिए यदि x < min, तो min := x अपडेट करें, x को स्टैक

  1. - पायथन में वैध एनाग्राम

    एनाग्राम मूल रूप से किसी दिए गए स्ट्रिंग या पैटर्न के सभी क्रमपरिवर्तन हैं। यह पैटर्न खोज एल्गोरिदम थोड़ा अलग है। इस मामले में, न केवल सटीक पैटर्न खोजा जाता है, यह टेक्स्ट में दिए गए पैटर्न के सभी संभावित व्यवस्थाओं को खोजता है। यदि इनपुट ANAGRAM और NAAGARM हैं, तो वे एनाग्राम हैं, लेकिन cat और fat

  1. - पायथन में वैध पालिंड्रोम

    मान लीजिए हमारे पास अल्फान्यूमेरिक मानों और प्रतीकों के साथ एक स्ट्रिंग है। लोअरकेस और अपरकेस अक्षर भी हैं। हमें जांचना है कि क्या स्ट्रिंग केवल लोअरकेस अक्षरों को ध्यान में रखते हुए पालिंड्रोम बना रही है या नहीं (अपरकेस को लोअरकेस में बदल दिया जाएगा), अन्य प्रतीकों जैसे कॉमा, स्पेस को नजरअंदाज किय