Pythonの部分文字列から回文を作成できます

文字列sがあるとすると、sの部分文字列に対してクエリを実行する必要があります。クエリクエリ[i]ごとに、3つの部分[左、右、k]があり、部分文字列s [左]、...、s [右]を再配置して、それらのうち最大k個を選択して置換することができます。小文字の英字。上記の操作の後でサブストリングが回文である可能性がある場合、クエリの結果はtrueです。それ以外の場合はfalse。配列answer[]を見つける必要があります。ここで、answer[i]はi番目のクエリクエリ[i]の結果です。

たとえば、入力が「abcda」の場合、クエリは[[3,3,0]、[1,2,0]、[0,3,1]、[0,3,2]、[0、 4,1]]の場合、出力は[true、false、false、true、true]

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

• solveと呼ばれるメソッドを定義します。これはdp行列とqを取ります。これは以下のように機能します-
• l：=q [0]、r：=q [1]、k：=q [2]、次にlとrを1増やし、1：=0
• 0〜25の範囲のiの場合
  • one：=one +（dp [r、i] – dp [l – 1、i]）mod 2
• 1/2の整数除算の場合はtrueを返します<=k、それ以外の場合はfalse
• makeDP（）と呼ばれる別のメソッドを定義します。これはdp行列とsを取ります。これは、以下のように機能します-
• 0からsの長さの範囲のiの場合
  • 0〜25の範囲のjの場合
    • dp [i、j]：=dp [i – 1、j]
  • dp [i、s[i]のASCII–「a」のASCII]を1増やします
• 主な方法は次のようになります-
• n：=文字列のサイズs、s：=“”連結s
• dp：=次数（n + 1）x 26の行列で、これを0で埋めます
• makeDP（dp、s）を呼び出す
• res：=qの長さと同じサイズの配列で、これをfalseで埋めます
• 0からq–1の長さの範囲のiの場合
  • res [i]：=resolve（dp、q [i]）
• return res

例（Python）

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

class Solution(object):
   def solve(self,dp,q):
      l = q[0]
      r = q[1]
      k = q[2]
      r+=1
      l+=1
      #arr = [ 0 for i in range(26)]
      one = 0
      for i in range(26):
         one += (dp[r][i]-dp[l-1][i])%2
      return one//2<=k
   def make_dp(self,dp,s):
      for i in range(1,len(s)):
         for j in range(26):
            dp[i][j] = dp[i-1][j]
         dp[i][ord(s[i])-ord('a')]+=1
   def canMakePaliQueries(self, s, q):
      n = len(s)
      s = " "+s
      dp = [[0 for i in range(26)] for j in range(n+1)]
      self.make_dp(dp,s)
      res = [False for i in range(len(q))]
      for i in range(len(q)):
         res[i] = self.solve(dp,q[i])
      return res
ob = Solution()
print(ob.canMakePaliQueries("abcda", [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]))

入力

"abcda"
[[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0,4,1]]

出力

[True, False, False, True, True]