পাইথনে O(1) স্পেস এবং O(N²) টাইম কমপ্লেক্সিটি দিয়ে ব্যালেন্সড প্যারেনথেসিস যাচাই করুন

সমস্যা বিবরণ

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

উদাহরণস্বরূপ, ইনপুট {([])} হলে আউটপুট হবে True।

সমাধানের ধাপসমূহ

1. cnt := 0, i := 0, j := -1 শুরু করুন।
2. solve(s, temp) ফাংশন সংজ্ঞায়িত করুন:
   • cnt ১ কমানো।
   • s-কে লিস্টে রূপান্তর করুন।
   • যদি j > -1 এবং s[j] == temp হয়, তবে s[i] এবং s[j] কে '#' দিয়ে প্রতিস্থাপন করুন, j কে পिछনে ले जाएं যতক্ষণ s[j] == '#', তারপর i বাড়ান এবং 1 রিটার্ন করুন।
   • অন্যথায় 0 রিটার্ন করুন।
3. মূল পদ্ধতিতে:
   • যদি স্ট্রিং খালি হয়, True রিটার্ন করুন।
   • ans := False সেট করুন।
   • যতক্ষণ i < len(s):
     • যদি s[i] == '}' হয়, ans := solve(s, '{'); যদি ans == 0 হয়, False রিটার্ন করুন।
     • যদি s[i] == ')' হয়, ans := solve(s, '('); যদি ans == 0 হয়, False রিটার্ন করুন।
     • যদি s[i] == ']' হয়, ans := solve(s, '['); যদি ans == 0 হয়, False রিটার্ন করুন।
     • অন্যথায় j := i, i := i + 1, cnt := cnt + 1।
   • যদি cnt != 0 হয়, False রিটার্ন করুন।
   • True রিটার্ন করুন।

পাইথন কোড উদাহরণ

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

ইনপুট

"{(()[])}"

আউটপুট

True