Pythonで特定の文字列を含む最小の部分文字列を見つけるプログラム

2つの文字列sとtがあるとします。 sで最小の部分文字列を見つける必要があります。ここで、tは部分文字列の部分列でもあります。そのタイプの部分文字列が存在しない場合は空白の文字列を返し、最小の部分文字列が複数ある場合は左端の文字列を取得します。

したがって、入力がs ="abcbfbghfb"、t ="fg"の場合、出力はfbg

これを解決するには、次の手順に従います-

• N：=Sのサイズ

• dp：=無限大で初期化されたサイズNの新しいリスト

• 0からN− 1の範囲のiの場合、実行

  • S[i]がT[0]と同じ場合、

    • dp [i]：=1

• 範囲1からT− 1のサイズのjの場合、実行

  • 最後：=新しい地図

  • dp2：=無限大で初期化されたサイズNの新しいリスト

  • 0からNの範囲のiの場合、実行

    • S[i]がT[j]と同じ場合、

      • prev_i：=最後から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