অর্ডার লিস্টে P (পিকআপ) এবং D (ডেলিভারি) অপারেশন থাকে। নিম্নলিখিত রুল মেনে চলতে হয়:
- পিকআপের আগে ডেলিভারি করা যাবে না।
- প্রতিটি পিকআপের ডেলিভারি হতে হবে।
- একবার পিকআপ ও ডেলিভারি হলে আবার সেটি করা যাবে না।
ইনপুট উদাহরণ
orders = ["P1", "D1", "P2", "P3", "D3", "D2"]আউটপুট: True
অ্যালগরিদম
- ডুপ্লিকেট অর্ডার চেক করুন (সেট লেংথ চেক)।
- ম্যাপ
aদিয়ে ট্র্যাক করুন: পিকআপ হলেa[id]=1, ডেলিভারি হলেa[id]--। - ডেলিভারির সময় আইডি ম্যাপে নাই তবে ইনভ্যালিড।
- শেষে সব ভ্যালু ০ হলে ভ্যালিড।
পাইথন কোড
def solve(orders):
a = {}
if len(set(orders)) != len(orders):
return False
for i in orders:
if i[0] == "P":
a[i[1:]] = 1
elif i[0] == "D":
if i[1:] not in a:
return False
else:
a[i[1:]] -= 1
return sum(a.values()) == 0
# টেস্ট
print(solve(["P1","D1","P2","P3","D3","D2"])) # Trueব্যাখ্যা
স্ট্যাকের মতো LIFO বাধ্য নয়, শুধু পিকআপ-ডেলিভারি অর্ডার এবং ইউনিকনেস চেক। সময় জটিলতা O(n)।
