Python
 Computer >> コンピューター >  >> プログラミング >> Python

Pythonで1回転した後の最長のパリンドローム部分文字列の長さを見つけるプログラム

文字列sがあり、任意のポイントで1回だけ回転できるとします。この操作を行うことで取得できる最長のパリンドローム部分文字列の長さを見つける必要があります。

したがって、入力がs ="elklev"の場合、出力は7になります。これは、"el"と"klev"の間で回転して、"levelk"を取得できるためです。したがって、ここでの最長のpalinfromicサブストリングの長さは5です。

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

  • s2：=sを2回連結する

  • max_len：=0

  • 範囲0からs− 1のサイズのxの場合、実行

    • 0からsのサイズまでの範囲のyについては、次のようにします

      • temp：=s2[インデックスxからx+yへ]

      • tempがパリンドロームでtempのサイズ>max_lenの場合、

        • max_len：=温度のサイズ

  • max_lenを返す

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

例

class Solution:
   def solve(self, s):
      s2 = 2 * s
      max_len = 0
      for x in range(len(s)):
         for y in range(len(s) + 1):
            temp = s2[x : x + y]
            if temp == temp[::−1] and len(temp) > max_len:
               max_len = len(temp)
      return max_len
ob = Solution()
s = "elklev"
print(ob.solve(s))

入力

"elklev"

出力

5

  1. Pythonで最長のアナグラムサブシーケンスの長さを見つけるプログラム

    2つの小文字の文字列SとTがあるとすると、最長のアナグラムサブシーケンスの長さを見つける必要があります。 したがって、入力がS =helloworld、T =hellorldの場合、出力は8になります これを解決するには、次の手順に従います- c：=新しいマップ、d：=新しいマップ 0からaのサイズの範囲のiの場合、実行 cのa[i]の場合、 c [a [i]]：=c [a [i]] + 1 それ以外の場合 c [a [i]]：=1 0からbのサイズの範囲のiの場合、実行 dのb[i]の場合、 d [b [i]]：=

  2. Pythonで最長の回文部分文字列

    文字列Sがあるとします。Sで最も長い回文部分文字列を見つける必要があります。文字列Sの長さは1000であると想定しています。したがって、文字列が「BABAC」の場合、その場合、最長の回文部分文字列は「BAB」です。 これを解決するために、次の手順に従います 文字列の長さと同じ次数の正方行列を1つ定義し、Falseで埋めます 主対角要素をtrueに設定して、0からorder –1までのすべてのiに対してDP[i、i] =True start：=0 範囲2からS+1の長さのlの場合 0からSの長さの範囲のiの場合– l + 1 end：=i + l l =2の場合、 S [i]