পাইথনে দুটি বৈধ বন্ধনী স্ট্রিংয়ের সর্বোচ্চ নেস্টিং গভীরতা

ধরুন আমাদের একটি স্ট্রিং আছে, সেই স্ট্রিংটি একটি বৈধ বন্ধনী স্ট্রিং (ভিপিএস নির্দেশিত) যদি এবং শুধুমাত্র যদি এটি শুধুমাত্র "(" এবং ")" অক্ষর নিয়ে থাকে, এবং এটি এই বৈশিষ্ট্যগুলিকে সন্তুষ্ট করে -

• এটি খালি স্ট্রিং, বা

• এটি AB হিসাবে লেখা যেতে পারে, যেখানে A এবং B VPS এর, অথবা

• এটি (A) হিসাবে লেখা যেতে পারে, যেখানে A একটি VPS৷

  ৷

আমরা নীচের মত যেকোন VPS S-এর নেস্টিং ডেপথ ডেপথ(S) সংজ্ঞায়িত করতে পারি -

• গভীরতা("") =0

• গভীরতা(A + B) =গভীরতার সর্বোচ্চ(A), গভীরতা(B), যেখানে A এবং B VPS এর

• গভীরতা("(" + A + ")") =1 + গভীরতা(A), যেখানে A একটি VPS।

যদি আমাদের একটি VPS সেক থাকে, তাহলে আমাদের এটিকে দুটি বিভক্ত করতে হবে A এবং B, যেমন A এবং B VPS এর (এবং A এর দৈর্ঘ্য + B এর দৈর্ঘ্য =seq এর দৈর্ঘ্য)। এখন যদি আমরা এইরকম A এবং B বেছে নিই যে সর্বোচ্চ(গভীরতা(A), গভীরতা(B)) হল ন্যূনতম সম্ভাব্য মান। তারপরে আমাদের একটি উত্তর অ্যারে (সেক এর দৈর্ঘ্যের) খুঁজে বের করতে হবে যা A এবং B-এর এই ধরনের পছন্দকে এনকোড করে:উত্তর[i] =0 যদি seq[i] A এর একটি অংশ হয়, অন্যথায় উত্তর[i] =1।

সুতরাং ইনপুট যদি "()(())()" এর মত হয়, তাহলে আউটপুট হবে [1,1,1,0,1,0,1,1]

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• n :=seq এর দৈর্ঘ্য, res :=0s এর একটি অ্যারে যার দৈর্ঘ্য n

• c1, c2 :=0, 0

• 0 থেকে n – 1

  রেঞ্জের i জন্য

  • যদি seq[i] ='('

    )

    • যদি c1

  • অন্যথায়

    • যদি c1> c2, তাহলে c1 কমিয়ে 1 করে, অন্যথায় c2 কমিয়ে 1 এবং res[i]:=1

• রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

class Solution(object):
   def maxDepthAfterSplit(self, seq):
      n = len(seq)
      res = [0] *n
      c1,c2= 0,0
      for i in range(n):
         if seq[i] == '(':
            if c1<c2:
               c1+=1
         else:
            c2+=1
            res[i]=1
      else:
         if c1>c2:
            c1-=1
         else:
            c2-=1
            res[i]=1
   return res
ob = Solution()
print(ob.maxDepthAfterSplit("()(())()"))

ইনপুট

"()(())()"

আউটপুট

[1, 1, 1, 0, 1, 0, 1, 1]