ধরুন আমাদের একটি স্ট্রিং আছে যা কিছু প্রাণীর প্রাথমিক অবস্থার প্রতিনিধিত্ব করছে। প্রতিটি প্রাণী তিনটি মানগুলির মধ্যে একটি নিতে পারে:L, প্রাণীটিকে বাম দিকে সরানো নির্দেশ করে। R, প্রাণীটিকে ডানদিকে সরানো নির্দেশ করে। @, ইঙ্গিত করে যে প্রাণীটি দাঁড়িয়ে আছে। একটি দিকে অগ্রসর হওয়া প্রাণীরা অন্যান্য প্রাণীকে তুলে নেবে যদি না প্রাণীটি বিপরীত দিক থেকে একটি শক্তি গ্রহণ করে। তারপর, এটি স্থির থাকবে। যখন প্রাণীটি নড়াচড়া বন্ধ করে তখন আমাদের প্রতিটি প্রাণীর অভিযোজন খুঁজে বের করতে হবে।
সুতরাং, যদি ইনপুট s ="@@L@R@@@@L" এর মত হয়, তাহলে আউটপুট হবে "LLL@RRRLLL"
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
মাত্রা :=s এর মতো আকারের একটি তালিকা এবং -1
দিয়ে পূরণ করুন -
q :=একটি ডবল শেষ সারি
-
আইডিএক্সের জন্য 0 থেকে s আকারের মধ্যে, করুন
-
যদি s[idx] "R" এর মত হয় বা s[idx] "L" এর মত হয়, তাহলে
-
q
এর শেষে সন্নিবেশ করুন (idx, 0, s[idx])
-
-
-
l :=s
এর অক্ষরের একটি নতুন তালিকা -
q খালি না থাকার সময়, করুন
-
(idx, new_level, dir) :=q এর বাম উপাদান, এবং এটি q থেকে মুছে দিন
-
যদি মাত্রা [idx] -1 এর মত হয়, তাহলে
-
স্তর [idx] :=new_level
-
l[idx] :=dir
-
যদি dir একই হয় "R" এবং idx + 1
-
q এর শেষে সন্নিবেশ করুন (idx + 1, new_level + 1, dir)
-
-
অন্যথায় যখন dir "L" এবং idx - 1>=0 এর মত হয়, তখন
-
সন্নিবেশ করুন (idx - 1, new_level + 1, dir) q এর শেষে
-
-
-
অন্যথায় যখন লেভেল[idx] new_level এর মত হয়, তখন
-
যদি l[idx] dir এর মত না হয়, তাহলে
-
l[idx] :="@"
-
-
-
-
l
এর উপাদান যোগ করে একটি স্ট্রিং ফেরত দিন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
from collections import deque class Solution: def solve(self, s): levels = [-1 for i in s] q = deque() for idx in range(len(s)): if s[idx] == "R" or s[idx] == "L": q.append((idx, 0, s[idx])) l = list(s) while q: idx, new_level, dir = q.popleft() if levels[idx] == -1: levels[idx] = new_level l[idx] = dir if dir == "R" and idx + 1 < len(l): q.append((idx + 1, new_level + 1, dir)) elif dir == "L" and idx - 1 >= 0: q.append((idx - 1, new_level + 1, dir)) elif levels[idx] == new_level: if l[idx] != dir: l[idx] = "@" return "".join(l) ob = Solution() s = "@@L@R@@@@L" print(ob.solve(s))
ইনপুট
"@@L@R@@@@L"
আউটপুট
LLL@RRRLLL