পাইথনে নির্দিষ্ট স্ট্রিং সম্বলিত সবচেয়ে ছোট সাবস্ট্রিং খুঁজে বের করার প্রোগ্রাম

মান লইয়া যাই আমাদের দুটি স্ট্রিং আছে s এবং t। আমাদের s-এ সবচেয়ে ছোট সাবস্ট্রিংটি খুঁজে বের করতে হবে, যেখানে t সাবস্ট্রিংটির একটি সাবসিকোয়েন্স (subsequence)। যদি এমন কোনো সাবস্ট্রিং না থাকে, তবে আমরা একটি খালি স্ট্রিং রিটার্ন করব, এবং যদি একাধিক সবচেয়ে ছোট সাবস্ট্রিং থাকে, তবে আমরা বামপাশের (leftmost) টি নিব।

তবে, ইনপুট যদি s = "abcbfbghfb", t = "fg" হয়, তবে আউটপুট হবে "fbg"।

এটি সমাধান করার জন্য আমরা নিচের ধাপগুলো অনুসরণ করব:

• N := S-এর আকার

• dp := N আকারের একটি নতুন লিস্ট যা ইনফিনিটি (infinity) দিয়ে আরম্ভ করা আছে

• for i in range 0 to N − 1, do

  • যদি S[i] T[0]-এর সমান হয়, তবে

    • dp[i] := 1

• for j in range 1 to size of T − 1, do

  • last := একটি নতুন ম্যাপ (map)

  • dp2 := N আকারের একটি নতুন লিস্ট যা ইনফিনিটি দিয়ে আরম্ভ করা আছে

  • for i in range 0 to N, do

    • যদি S[i] T[j]-এর সমান হয়, তবে

      • prev_i := last থেকে T[j − 1]-এর মান রিটার্ন করুন

      • যদি prev_i null না হয়, তবে

        • dp2[i] := dp[prev_i] + (i − prev_i)

      • last[S[i]] := i

    • dp := dp2

  • m := dp-এর ন্যূনতম মান

  • i := dp-এ m সম্বলিত ইন্ডেক্স

  • যদি m ইনফিনিটি হয়, তবে

    • খালি স্ট্রিং রিটার্ন করুন

  • S[i − dp[i] + 1 থেকে i] রিটার্ন করুন

  বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন:

  উদাহরণ

  class Solution:
      def solve(self, S, T):
          INF = float("inf")
          N = len(S)
          dp = [INF] * N
          
          for i in range(N):
              if S[i] == T[0]:
                  dp[i] = 1
          
          for j in range(1, len(T)):
              last = {}
              dp2 = [INF] * N
              
              for i in range(N):
                  if S[i] == T[j]:
                      prev_i = last.get(T[j - 1], None)
                      if prev_i is not None:
                          dp2[i] = dp[prev_i] + (i - prev_i)
                  last[S[i]] = i
              
              dp = dp2
          
          m = min(dp)
          i = dp.index(m)
          
          if m == INF:
              return ""
          
          return S[i - dp[i] + 1 : i + 1]
  
  ob = Solution()
  print(ob.solve("abcbfbghfb", "fg"))

  ইনপুট

  "abcbfbghfb","fg"

  আউটপুট

  fbg