Pythonで回文部分文字列の数をカウントするプログラム

文字列sがあるとすると、s内の回文部分文字列の数を見つける必要があります。

したがって、入力がs ="level"のような場合、パリンドロームのサブストリングは["l"、 "e"、 "v"、 "e"、 "l"、 "eve"であるため、出力は7になります。 、"レベル"]

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

• 関数check_palindrome（）を定義します。これには、文字列、左、右が必要です
• ans：=0
• 左>=0、右
• s[左]がs[右]と同じ場合、
  • ans：=ans + 1
  • 左：=左-1
  • 右：=右+1
• それ以外の場合、
  • 回答を返す

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

例

class Solution:
   def solve(self, s):
      def check_palindrome(string, left, right):
         ans = 0
         while left >= 0 and right < len(s):
            if s[left] == s[right]:
               ans += 1
               left -= 1
               right += 1
            else:
               return ans
         return ans
      ans = 0
      for char_index in range(len(s)):
         ans += check_palindrome(s, char_index - 1, char_index + 1)
         ans += check_palindrome(s, char_index, char_index + 1)
      return (ans) + len(s)
ob = Solution()
print(ob.solve("level"))

入力

"level"

出力

7