Pythonで最短のスーパーシーケンスの長さを見つけるプログラム

2つの文字列sとtがあるとします。サブシーケンスとしてsとtの両方を持つ最短の文字列の長さを見つける必要があります。

したがって、入力がs ="pipe" t ="people"のような場合、可能なスーパーシーケンスの1つは "pieople"であるため、出力は7になります。

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

• m：=sのサイズ、n：=tのサイズ

• table：=サイズ（n + 1）x（m + 1）のテーブルで、0を入力します

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

  • 0からnの範囲のjについては、次のようにします

    • iが0と同じか、jが0と同じ場合、

      • table [i、j]：=0

    • それ以外の場合

      • s[i-1]がt[j-1]と同じ場合、

        • table [i、j]：=1 + table [i-1、j-1]

      • それ以外の場合

        • table [i、j] =table [i、j-1]とtable [i-1、j]

          の最大値

• m +nを返す-table[m、n]

例

理解を深めるために、次の実装を見てみましょう-

class Solution:
   def solve(self, s, t):
      m = len(s)
      n = len(t)
      table = [[0 for i in range(n + 1)] for j in range(m + 1)]
      for i in range(m + 1):
         for j in range(n + 1):
            if i == 0 or j == 0:
               table[i][j] = 0
            else:
               if s[i - 1] == t[j - 1]:
                  table[i][j] = 1 + table[i - 1][j - 1]
            else:
               table[i][j] = max(table[i][j - 1], table[i - 1][j])
      return m + n - table[m][n]
ob = Solution()
s = "pipe"
t = "people"
print(ob.solve(s, t))

入力

"pipe", "people"

出力

7