home

หน้าแรก
 Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> C++

Palindrome Partitioning III ใน C ++

สมมติว่าเรามีสตริง s ที่มีตัวอักษรพิมพ์เล็กและจำนวนเต็ม k เราต้องรักษาคุณสมบัติบางอย่างไว้ เหล่านี้คือ −

  • ขั้นแรก เราต้องเปลี่ยนอักขระบางตัว (ถ้าจำเป็น) ของ s เป็นตัวอักษรภาษาอังกฤษตัวพิมพ์เล็กอื่นๆ
  • จากนั้นแบ่งสตริง s เป็น k สตริงย่อย เพื่อให้แต่ละสตริงย่อยเป็นพาลินโดรม

เราต้องหาจำนวนอักขระขั้นต่ำที่เราต้องเปลี่ยนเพื่อแบ่งสตริง

ดังนั้นหากสตริงนั้นเหมือนกับ "abbc" และ k =2 คำตอบจะเป็น 1 เนื่องจากเราต้องเปลี่ยนอักขระหนึ่งตัวเพื่อแยกสตริงนี้เป็นสองสตริง palindrome ดังนั้นหากเราเปลี่ยน c เป็น b หรือ b อันสุดท้ายเป็น c เราก็จะได้พาลินโดรมหนึ่งอัน เช่น "bbb" หรือ "cbc" และพาลินโดรมอีกอันคือ "aba"

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

  • กำหนดบันทึกอาร์เรย์ขนาด:105 x 105
  • กำหนดฟังก์ชัน Solve() จะใช้ s, idx, k, 2D array> dp,
  • ถ้า idx เท่ากับขนาดของ s แล้ว −
    • คืนค่าเมื่อ k เป็น 0 แล้ว 0 มิฉะนั้น 1000
  • ถ้าบันทึก[idx][k] ไม่เท่ากับ -1 แล้ว −
    • return memo[idx][k]
  • ถ้า k <=0 แล้ว −
    • ผลตอบแทน
  • ตอบ :=inf
  • สำหรับการเริ่มต้น i :=idx เมื่อฉัน <ขนาดของ s อัปเดต (เพิ่ม i ขึ้น 1) ทำ −
    • ans :=ขั้นต่ำของ ans และ dp[idx][i] + เรียกใช้ฟังก์ชัน Solve(s, i + 1, k - 1, dp)
  • return memo[idx][k] =ans
  • จากวิธีหลัก ให้ทำดังนี้
  • n :=ขนาดของ s
  • กรอกบันทึกด้วย -1
  • กำหนดอาร์เรย์ 2 มิติหนึ่ง dp ที่มีขนาด n x n
  • สำหรับการเริ่มต้น l :=2 เมื่อ l <=n อัปเดต (เพิ่ม l ขึ้น 1) ทำ −
    • สำหรับการเริ่มต้น i :=0, j :=l - 1, เมื่อ j
    • ถ้า l เท่ากับ 2 แล้ว −
    • dp[i][j] :=true เมื่อ s[i] ไม่เหมือนกับ s[j]
    • มิฉะนั้น
      • dp[i][j] :=dp[i + 1][j - 1] + 0 เมื่อ s[i] เหมือนกับ s[j]
  • ผลตอบแทนการแก้(s, 0, k, dp)

    • ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

    ตัวอย่าง

    #include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   int memo[105][105];
   lli solve(string s, int idx, int k, vector < vector <int> > &dp){
      if(idx == s.size()) {
         return k == 0? 0 : 1000;
      }
      if(memo[idx][k] != -1) return memo[idx][k];
      if(k <= 0)return INT_MAX;
      lli ans = INT_MAX;
      for(int i = idx; i < s.size(); i++){
         ans = min(ans, dp[idx][i] + solve(s, i + 1, k - 1, dp));
      }
      return memo[idx][k] = ans;
   }
   int palindromePartition(string s, int k) {
      int n = s.size();
      memset(memo, -1, sizeof(memo));
      vector < vector <int> > dp(n, vector <int>(n));
      for(int l =2; l <= n; l++){
         for(int i = 0, j = l - 1; j <n; j++, i++){
            if(l==2){
               dp[i][j] = !(s[i] == s[j]);
            }else{
               dp[i][j] = dp[i+1][j-1] + !(s[i] == s[j]);
            }
         }
      }
      return solve(s, 0, k, dp);
   }
};
main(){
   Solution ob;
   cout << (ob.palindromePartition("ababbc", 2));
}

    อินพุต

    “ababbc”

    ผลลัพธ์

    1