Có thể tạo Palindrome từ chuỗi con trong Python

Giả sử chúng ta có một chuỗi s, chúng ta phải thực hiện các truy vấn trên các chuỗi con của s. Đối với mỗi truy vấn truy vấn [i], có ba phần [trái, phải, k], chúng tôi có thể sắp xếp lại chuỗi con s [trái], ..., s [phải], sau đó chọn tối đa k trong số chúng để thay thế bằng bất kỳ ký tự tiếng Anh viết thường nào. Nếu chuỗi con có thể là một palindrome sau các phép toán được đề cập ở trên, thì kết quả của truy vấn là true. Ngược lại là false. Chúng ta phải tìm một câu trả lời mảng [], trong đó câu trả lời [i] là kết quả của các truy vấn thứ i [i].

Ví dụ:nếu đầu vào là “abcda”, các truy vấn giống như [[3,3,0], [1,2,0], [0,3,1], [0,3,2], [0, 4,1]], thì đầu ra sẽ là [true, false, false, true, true]

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một phương pháp được gọi là giải quyết, điều này sẽ nhận ma trận dp và q. Điều này sẽ hoạt động như dưới đây -
• l:=q [0], r:=q [1], k:=q [2], sau đó tăng l và r thêm 1, một:=0
• cho tôi trong phạm vi từ 0 đến 25
  • one:=one + (dp [r, i] - dp [l - 1, i]) mod 2
• trả về true, khi phép chia số nguyên của một / 2 <=k, ngược lại là false
• Xác định một phương thức khác được gọi là makeDP (), phương thức này sẽ sử dụng ma trận dp và s, phương thức này sẽ hoạt động như bên dưới -
• cho tôi trong phạm vi từ 0 đến độ dài là s
  • cho j trong phạm vi từ 0 đến 25
    • dp [i, j]:=dp [i - 1, j]
  • tăng dp [i, ASCII của s [i] - ASCII của ‘a’] lên 1
• Phương pháp chính sẽ giống như -
• n:=kích thước của chuỗi s, s:=“” nối s
• dp:=ma trận có bậc (n + 1) x 26 và điền vào giá trị này bằng 0
• gọi makeDP (dp, s)
• res:=một mảng có kích thước bằng với chiều dài của q và điền vào giá trị này bằng false
• cho tôi trong phạm vi từ 0 đến độ dài của q - 1
  • res [i]:=giải quyết (dp, q [i])
• trả lại res

Ví dụ (Python)

Hãy cùng chúng tôi xem cách triển khai sau đây để hiểu rõ hơn -

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]]))

Đầu vào

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

Đầu ra

[True, False, False, True, True]