Python의 하위 문자열에서 회문을 만들 수 있음

문자열 s가 있다고 가정하고 s의 하위 문자열에 대해 쿼리를 작성해야 합니다. 각 쿼리 쿼리[i]에는 [왼쪽, 오른쪽, k]의 세 부분이 있습니다. 하위 문자열 s[left], ..., s[right]를 재배열한 다음 그 중 최대 k개를 선택하여 바꿀 수 있습니다. 모든 소문자 영어. 위에서 언급한 작업 후에 부분 문자열이 회문일 수 있는 경우 쿼리 결과는 true입니다. 그렇지 않으면 거짓입니다. 배열 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에 대해
  • 하나 :=하나 + (dp[r, i] – dp[l – 1, i]) 모드 2
• 1/2의 정수 나눗셈이 <=k일 때 true를 반환하고, 그렇지 않으면 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] :=해결(dp, q[i])
• 반환 결과

예시(파이썬)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

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]