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

Pythonですべての回文部分文字列の長さが奇数かどうかを確認するプログラム

文字列 s が与えられたとき、そのすべての回文部分文字列の長さが奇数であるかどうかを判定する必要があります。

例えば、入力が s = "level" の場合、出力は True になります。

解法のアプローチ

この問題は、以下の手順で解くことができます。

  • インデックス 1 から文字列の長さまでの範囲で i をループします
  • s[i] と s[i - 1] が同じ文字であれば、False を返します
  • ループが最後まで完了すれば、True を返します

なぜこの方法で正しく判定できるのか

ポイントは、偶数長の回文は必ず中央に同じ文字が隣接して並ぶペアを含むという性質です。つまり、隣り合う2つの文字がすべて異なるのであれば、偶数長の回文部分文字列は存在しないことになります。そのため、文字列全体を走査して隣接する文字のペアをチェックするだけで、この問題を判定できます。

実装例

class Solution:
   def solve(self, s):
      for i in range(1, len(s)):
         if s[i] == s[i - 1]:
            return False
      return True

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

入力

"level"

出力

True

計算量について

このアルゴリズムは文字列を一度だけ走査するため、時間計算量は O(n) であり、追加のメモリも不要なため空間計算量は O(1) となります。非常にシンプルかつ効率的な解法です。

  1. Pythonで2つの二分木の葉の並び（シーケンス）が同じかどうかを確認する方法

    はじめに2つの二分木が与えられたとき、それぞれの木を左から右へたどったときの葉ノードの並び（シーケンス）が一致しているかどうかを判定する問題を考えてみましょう。例えば、次のような2つの木が入力として与えられた場合を想定します。この場合、どちらの木も葉の並びは [2, 6] となるため、出力は True になります。解決のアプローチこの問題を解くためには、以下の手順に従います。結果を格納するための新しいリスト c を用意します。inorder() 関数を定義します。この関数はルートノードとリスト c を引数に取ります。c が null の場合は、新しい空のリストを作成します。ルートノードが nu

  2. Pythonで二分木のすべてのノードの値が同じかどうかをチェックするプログラム

    問題の概要二分木が与えられたとき、その木に含まれるすべてのノードが同じ値を持っているかどうかを判定することを考えます。例えば、次のような二分木が入力として与えられた場合、すべてのノードが同じ値を持っているため、出力は True になります。解決のアプローチこの問題は、再帰を使ってシンプルに解くことができます。以下の手順に従います。solve() 関数を定義します。この関数は root(現在のノード)と val(比較対象の値)を引数として受け取ります。root が null(None)の場合は、True を返します。空の部分木は条件を満たしているとみなせるためです。val が未定義の場合は、ro