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

Pythonで回文を分割する方法の数を見つけるためのプログラム

文字列sがあるとすると、各部分が回文になるように文字列を分割できる方法の数を見つける必要があります。

したがって、入力がs ="xyyx"の場合、出力は3になります。これは、["x"、 "yy"、 "x"]、["x"、 "y"、"のように分割されるためです。 y "、" x "]、["xyyx"]。

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

  • n：=sのサイズ
  • table：=サイズn + 1のリストで、0で埋めます
  • table [0]：=1
  • 0からnの範囲のiについては、
    • 0からi-1の範囲のjの場合、do
      • sub：=s[インデックスjからiへ]
      • subが回文の場合、
        • table [i]：=table [i] + table [j]
  • テーブルの最後の要素を返す

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

例

class Solution:
   def solve(self, s):
      n = len(s)
      table = [1] + [0] * n
      for i in range(n + 1):
         for j in range(i):
            sub = s[j:i]
            if sub == sub[::-1]:
               table[i] += table[j]
      return table[-1]

ob = Solution()
s = "xyyx"
print(ob.solve(s))

入力

"xyyx"

出力

3

  1. Pythonで収集できるコインの最大数を見つけるためのプログラム

    各セルにいくつかのコインが格納されている2Dマトリックスがあるとします。 [0,0]から始めて、右または下にしか移動できない場合、右下隅で収集できるコインの最大数を見つける必要があります。 したがって、入力が次のような場合 1 4 2 2 0 0 0 5 [1、4、2、2、5] のパスをたどると、出力は14になります。 これを解決するために、次の手順に従います- 範囲1からAの行数までのrについては、次のようにします A [r、0]：=A [r、0] + A [r-1、0] 範囲1からAの列数までのcにつ

  2. Pythonで階段を上る方法をいくつ見つけるかをプログラムする

    n段の階段があり、一度に1段または2段の階段を上ることができるとします。階段を上るユニークな方法の数を返す関数を定義する必要があります。 ステップの順序は変更しないでください。そのため、ステップの異なる順序はそれぞれ1つの方法としてカウントされます。答えが非常に大きい場合は、結果を10 ^ 9+7で変更します したがって、入力がn =5のような場合、8つの固有の方法があるため、出力は8になります- 1、1、1、1、1 2、1、1、1 1、2、1、1 1、1、2、1 1、1、1、2 1、2、2 2、1、2 2、2、1 これを解決するには、次の手順に従いま