পাইথনে O(1) স্পেস O(N^2) সময় জটিলতার একটি অভিব্যক্তিতে সুষম বন্ধনী পরীক্ষা করুন

ধরুন আমাদের কাছে '(','), '{', '}', '[' এবং ']' এই বন্ধনীগুলি সম্বলিত একটি স্ট্রিং স্ট্র আছে, আমাদের পরীক্ষা করতে হবে বন্ধনীগুলি ভারসাম্যপূর্ণ কিনা। আমরা বলতে পারি বন্ধনী ভারসাম্যপূর্ণ যখন খোলা এবং বন্ধ বন্ধনীর ধরন একই ধরণের হয়। বন্ধনী সঠিক ক্রমে বন্ধ করা হয়।

সুতরাং, ইনপুট যদি {([])} এর মত হয়, তাহলে আউটপুট হবে True।

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

• cnt :=0
• i :=0
• j :=-1
• একটি ফাংশন সংজ্ঞায়িত করুন solve()। এটি s, temp
লাগবে
• cnt :=cnt - 1
• s :=s থেকে একটি নতুন তালিকা
• যদি j> -1 এবং s[j] temp এর মত হয়, তাহলে
  • s[i] :='#'
  • s[j] :='#'
  • যদিও j>=0 এবং s[j] '#' এর মতো, do
    • j :=j - 1
  • i :=i + 1>
  • প্রত্যাবর্তন 1
• অন্যথায়,
  • রিটার্ন 0
• প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
• যদি s-এর আকার 0 এর সমান হয়, তাহলে
  • সত্য ফেরান
• অন্যথায়,
  • উত্তর :=মিথ্যা
  • যখন i
  • যদি s[i] '}' এর মত হয়, তাহলে
    • উত্তর :=সমাধান(গুলি, '{')
    • যদি উত্তর 0 এর মত হয়, তাহলে
      • মিথ্যে ফেরত দিন
    • অন্যথায় যখন s[i] ')' এর মত হয়, তাহলে
      • উত্তর :=সমাধান(গুলি, '(')
      • যদি উত্তর 0 এর মত হয়, তাহলে
        • মিথ্যে ফেরত দিন
    • অন্যথায় যখন s[i] ']' এর মত হয়, তখন
      • উত্তর :=সমাধান(গুলি, '[')
      • যদি উত্তর 0 এর মত হয়, তাহলে
        • মিথ্যে ফেরত দিন
    • অন্যথায়,
      • j :=i
      • i :=i + 1
      • cnt :=cnt + 1
• যদি cnt 0 এর মত না হয়, তাহলে
  • মিথ্যে ফেরত দিন
• সত্য ফেরান

cnt = 0
i = 0
j = -1
def solve(s, temp):
   global i, j, cnt
   cnt -= 1
   s = list(s)
   if j > -1 and s[j] == temp:
      s[i] = '#'
      s[j] = '#'
      while j >= 0 and s[j] == '#':
         j -= 1
      i += 1
      return 1
   else:
      return 0
def bracketOrderCheck(s):
   global i, j, cnt
   if len(s) == 0:
      return True
   else:
      ans = False
      while i < len(s):
         if s[i] == '}':
            ans = solve(s, '{')
            if ans == 0:
               return False
         elif s[i] == ')':
            ans = solve(s, '(')
            if ans == 0:
               return False
         elif s[i] == ']':
            ans = solve(s, '[')
            if ans == 0:
               return False
         else:
            j = i
            i += 1
            cnt += 1
      if cnt != 0:
         return False
      return True
print(bracketOrderCheck("{([])}"))

"{(()[])}"

True