পাইথনে '?' রিপ্লেস করে কোনো দুটি এডজেসেন্ট ডিজিট সমান না হয় এমন ছোটতম সংখ্যা বানানো

স্ট্রিং s এ 1, 2, 3, ? ক্যারেক্টার থাকে। ? কে 1, 2, 3-এর যেকোনো দিয়ে রিপ্লেস করুন যাতে কোনো দুটি এডজেসেন্ট ডিজিট সমান নয় এবং ফলাফল সবচেয়ে ছোট হয়।

ইনপুট উদাহরণ

s = "2??3?"

আউটপুট: 21231

অ্যালগরিদম

লেফট-টু-রাইট গ্রিডি: প্রতিটি ?-এর জন্য বাম ও ডান পাশের ডিজিট দেখে সবচেয়ে ছোট সম্ভাব্য ডিজিট (১, ২, ৩) বেছে নিন যা উভয় পাশের সাথে মিলে না।

পাইথন কোড

def solve(s):
    i = 0
    s = list(s)
    if len(s) < 2:
        if s[i] == "?":
            return "1"
    while i < len(s):
        if s[i] == "?":
            if i == 0:
                s[i] = "1" if s[i+1] != "1" else "2"
            elif i > 0 and i <= len(s) - 2:
                if s[i-1] == "1":
                    s[i] = "3" if s[i+1] == "2" else "2"
                elif s[i-1] == "2":
                    s[i] = "3" if s[i+1] == "1" else "1"
                elif s[i-1] == "3":
                    s[i] = "2" if s[i+1] == "1" else "1"
            else:  # last char
                s[i] = "1" if s[i-1] != "1" else "2"
        i += 1
    return "".join(s)

# টেস্ট
print(solve("2??3?"))  # 21231

ব্যাখ্যা

গ্রিডি কাজ করে কারণ শুধু ৩ ডিজিট (১,২,৩) এবং লোকাল কনস্ট্রেইন্ট। সবচেয়ে ছোট ডিজিট বেছে নেওয়া গ্লোবালি অপ্টিমাল।