สามารถสร้าง Palindrome จากสตริงย่อยใน Python

สมมติว่าเรามีสตริง s เราต้องทำการค้นหาในสตริงย่อยของ s สำหรับแต่ละเคียวรีแบบสอบถาม[i] มีสามส่วน [left, right, k] เราอาจจัดเรียงสตริงย่อยใหม่ s[left], ..., s[right] แล้วเลือกมากถึง k รายการเพื่อแทนที่ด้วย ตัวอักษรภาษาอังกฤษตัวพิมพ์เล็กใด ๆ ถ้าสตริงย่อยเป็นไปได้ที่จะเป็นพาลินโดรมหลังจากการดำเนินการที่กล่าวถึงข้างต้น ผลลัพธ์ของการสืบค้นจะเป็นจริง มิฉะนั้นเท็จ เราต้องหาคำตอบของอาร์เรย์[] โดยที่ answer[i] คือผลลัพธ์ของการสืบค้นที่ i-th[i]

ตัวอย่างเช่น หากอินพุตคือ “abcda” ข้อความค้นหาจะเหมือนกับ [[3,3,0],[1,2,0],[0,3,1],[0,3,2],[0, 4,1]] จากนั้นผลลัพธ์จะเป็น [จริง, เท็จ, เท็จ, จริง, จริง]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดวิธีการที่เรียกว่า Solve ซึ่งจะใช้ dp matrix และ q สิ่งนี้จะทำงานเหมือนด้านล่าง −
• l :=q[0], r :=q[1], k :=q[2] จากนั้นเพิ่ม l และ r ขึ้น 1 หนึ่ง :=0
• สำหรับ i ในช่วง 0 ถึง 25
  • หนึ่ง :=หนึ่ง + (dp[r, i] – dp[l – 1, i]) mod 2
• คืนค่า จริง เมื่อหารจำนวนเต็มของ 1 / 2 <=k มิฉะนั้น เท็จ
• กำหนดเมธอดอื่นที่เรียกว่า makeDP() ซึ่งจะใช้เมทริกซ์ dp และ s ซึ่งจะทำงานดังนี้ −
• สำหรับ i ในช่วง 0 ถึงความยาวของ s
  • สำหรับ j ในช่วง 0 ถึง 25
    • dp[i, j] :=dp[i – 1, j]
  • เพิ่ม dp[i, ASCII ของ s[i] – ASCII ของ 'a'] ขึ้น 1
• วิธีการหลักจะเป็นเช่น −
• n :=ขนาดของสตริง s, s :=“ ” ต่อ s
• dp :=เมทริกซ์ของคำสั่ง (n + 1) x 26 และเติมด้วย 0
• โทร makeDP(dp, s)
• res :=อาร์เรย์ที่มีขนาดเท่ากับความยาวของ q และเติมด้วย false
• สำหรับ i ในช่วง 0 ถึงความยาวของ q – 1
  • res[i] :=แก้(dp, q[i])
• ผลตอบแทน

ตัวอย่าง(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]