تقسيم Palindrome  


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون Facebook جوجل Microsoft
التراجع عمق البحث الأول البرمجة الديناميكية خيط

المشكلة بيان  

عند إعطاء سلسلة ، ابحث عن الحد الأدنى لعدد القطع المطلوبة بحيث تكون جميع السلاسل الفرعية للأقسام متجانسة. نظرًا لأننا نقطع السلسلة الأصلية إلى أقسام مختلفة بحيث تكون جميع السلاسل الفرعية متجانسة ، فإننا نطلق على هذه المشكلة مشكلة قسم Palindrome.

مثال   

asaaaassss
2

شرح: هنا ، يمكننا قص سلسلة الإدخال كـ آسا | aaa | ssss وبالتالي نحن بحاجة إلى قطعتين.

zxxzxxzyuy
1

شرح: هنا ، يمكننا قص سلسلة الإدخال كـ zxxzxxz | yuy، لذلك نحن بحاجة إلى قطع واحد.

 

نهج لتقسيم Palindrome  

نهج ساذج

أول ما يتبادر إلى الذهن هو حل تكراري بسيط. ضع في اعتبارك أن لدينا سلسلة بطول يقول n. الآن ، إذا كانت السلسلة متناظرة ، فيمكننا ببساطة إرجاع الإجابة 0 ولكن إذا لم تكن متناظرة. نحاول جميع الاحتمالات ، ما أعنيه هو أننا نحاول قطع السلسلة إلى قسمين في الفهرس k ثم نحلها بشكل متكرر للجزء الأيسر والجزء الأيمن بشكل منفصل. هذا الحل صحيح تمامًا ولكنه غير فعال.

minCut(string s, int i, int j) = 1 + min( minCut(s, i, k) + minCut(s, k+1, j) )

where k ranges from i to j

i, j, k are indices on string

تقسيم Palindrome

نهج فعال

حتى الآن ، نحن نعرف حلاً بسيطًا يحل الجزء الأيسر والجزء الأيمن من الخيط مع وضع قطع بينهما. لذا ، يمكننا القول أنه في البداية كانت لدينا مشكلة في سلسلة من الحجم n ثم اختزلنا مشكلتنا إلى مشكلتين فرعيتين. إذا رأينا بنية المشاكل الفرعية فإنها بالتأكيد تتداخل أيضًا. لذلك ، هذا يشير إلى استخدام البرمجة الديناميكية لتقليل التعقيد الزمني الأسي للحل السابق لـ O (N ^ 3). يوضح الشكل المشكلات الفرعية المتداخلة باللون الأحمر. مشابه البرمجة الديناميكية يمكن رؤية النمط في مشكلة ضرب سلسلة المصفوفة، حيث نقوم أولاً بحل المشكلات الفرعية الأصغر ثم نجمع نتائجها لحل المشكلة الأصلية.

رمز تقسيم Palindrome  

كود C ++

#include <bits/stdc++.h>
using namespace std;

int minCut(string s) {
    int n = s.length();
    vector<vector<int>> cuts;
    vector<vector<bool>> isPalindrome;
    cuts.assign(n,vector<int>(n, INT_MAX));
    isPalindrome.assign(n, vector<bool>(n, false));
    
    for(int len = 1;len<=n;len++) {
        for(int i=0;i<n-len+1;i++) {
            int j = i+len-1;
            if(len <= 2)
                isPalindrome[i][j] = s[i] == s[j];
            else
                isPalindrome[i][j] = s[i] == s[j] && isPalindrome[i+1][j-1];
            
            if(isPalindrome[i][j]) {
                cuts[i][j] = 0;
            } else {
                for(int k=i;k<j;k++)
                    cuts[i][j] = min(cuts[i][j], 1+cuts[i][k]+cuts[k+1][j]);
            }
        }
    }
    return cuts[0][n-1];
}

int main() {
  int t;cin>>t;
  while(t--){
      string s;
      cin>>s;
      cout<<minCut(s)<<endl;
  }
}

كود جافا

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static int minCut(String s) {
        int n = s.length();
        int cuts[][] = new int[n][n];
        boolean isPalindrome[][] = new boolean[n][n];
        
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                cuts[i][j] = Integer.MAX_VALUE;
            }
        }
        
        for(int len = 1;len<=n;len++) {
            for(int i=0;i<n-len+1;i++) {
                int j = i+len-1;
                if(len <= 2)
                    isPalindrome[i][j] = s.charAt(i) == s.charAt(j);
                else
                    isPalindrome[i][j] = s.charAt(i) == s.charAt(j) && isPalindrome[i+1][j-1];
                
                if(isPalindrome[i][j]) {
                    cuts[i][j] = 0;
                } else {
                    for(int k=i;k<j;k++)
                        cuts[i][j] = Math.min(cuts[i][j], 1+cuts[i][k]+cuts[k+1][j]);
                }
            }
        }
        return cuts[0][n-1];    
    }
    
  public static void main (String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());
    while(t-- > 0) {
        String s = br.readLine();
        int ans = minCut(s);
        System.out.println(ans);
    }
  }
}

تعقيد الوقت: O (N ^ 3)

تبدأ الحلقة الأولى من 1 إلى n (len = 1 to len = n)

الحلقة المتداخلة التي توضح فهرس البداية للمشكلة الفرعية (i) تعمل من 0 إلى n-len

أكثر حلقة داخلية ، والتي تنص على مؤشر القطع بين k و k + 1 ، تعمل أيضًا من i إلى j. 

وبالتالي ، في أسوأ الحالات ، يُقال أن التعقيد الزمني هو O (N ^ 3).

التعقيد المكاني: O (N ^ 2)

لدينا مصفوفتان هما Palindrome والقطع وهما عبارة عن مصفوفات ثنائية الأبعاد وبالتالي لدينا O (N ^ 2) تعقيد مساحة.

انظر أيضا
صفيف الفرق | استعلام تحديث النطاق في O (1)

 

الحل الأمثل لتقسيم Palindrome  

يمكننا تقليل تعقيد الوقت إلى O (N ^ 2)، عن طريق الحساب المسبق لمصفوفة isPalindrome. ثم بدلاً من تخزين التخفيضات للسلسلة الفرعية من i إلى j (حيث i هو الحد الأيسر و j هو الحد الأيمن لأي سلسلة فرعية متناظرة) ، نقوم بتخزين القطع كمصفوفة أحادية البعد تخزن الحد الأدنى لعدد القطع المطلوبة لبدء السلسلة الفرعية من 0 إلى أنا. تعمل الحلقة الداخلية على j من 0 إلى i-1 ، حيث نتحقق مما إذا كانت السلسلة الفرعية [j ، i] متناظرة؟ إذا كانت السلسلة الفرعية متناظرة ، فإن السلسلة الفرعية [j، i] لها نفس عدد القطع كما في السلسلة الفرعية [0، j-1] + 1. لذلك ، نقوم فقط بتحديث الإجابة عن طريق تخزين الحد الأدنى من جميع خيارات j من 0 إلى i-1. بهذه الطريقة ، في النهاية ، لدينا الحد الأدنى من التخفيضات المطلوبة بحيث تكون جميع الأقسام متجانسة.

كود C ++

#include <bits/stdc++.h>
using namespace std;

int minCut(string s) {
    int n = s.length();
    vector<int> cuts;
    vector<vector<bool>> isPalindrome;
    cuts.assign(n,INT_MAX);
    isPalindrome.assign(n, vector<bool>(n, false));
    
    for(int len = 1;len<=n;len++) {
        for(int i=0;i<n-len+1;i++) {
            int j = i+len-1;
            if(len <= 2)
                isPalindrome[i][j] = s[i] == s[j];
            else
                isPalindrome[i][j] = s[i] == s[j] && isPalindrome[i+1][j-1];
        }
    }
    
    cuts[0] = 0;
    for(int i=1;i<n;i++) {
        for(int j=1;j<=i;j++)
            if(isPalindrome[0][i])
                cuts[i] = 0;
            else if(isPalindrome[j][i])
                cuts[i] = min(cuts[i], 1 + cuts[j-1]);
    }
    return cuts[n-1];
}

int main() {
  int t;cin>>t;
  while(t--){
      string s;
      cin>>s;
      cout<<minCut(s)<<endl;
  }
}

كود جافا

import java.util.*;
import java.lang.*;
import java.io.*;

class Main {
    public static int minCut(String s) {
        int n = s.length();
        int cuts[] = new int[n];
        boolean isPalindrome[][] = new boolean[n][n];
        
        for(int i=0;i<n;i++) {
            cuts[i] = Integer.MAX_VALUE;
        }
        
        for(int len = 1;len<=n;len++) {
            for(int i=0;i<n-len+1;i++) {
                int j = i+len-1;
                if(len <= 2)
                    isPalindrome[i][j] = s.charAt(i) == s.charAt(j);
                else
                    isPalindrome[i][j] = s.charAt(i) == s.charAt(j) && isPalindrome[i+1][j-1];
            }
        }
        
        cuts[0] = 0;
        for(int i=1;i<n;i++) {
            for(int j=1;j<=i;j++)
                if(isPalindrome[0][i])
                    cuts[i] = 0;
                else if(isPalindrome[j][i])
                    cuts[i] = Math.min(cuts[i], 1 + cuts[j-1]);
        }
        return cuts[n-1];
    }
    
  public static void main (String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    int t = Integer.parseInt(br.readLine());
    while(t-- > 0) {
        String s = br.readLine();
        int ans = minCut(s);
        System.out.println(ans);
    }
  }
}

تعقيد الوقت: O (N ^ 2)

أخذنا O (N ^ 2) للتخزين إذا كانت السلسلة الفرعية من الفهرس إلى j متناظرة.

ال ، O (N ^ 2) لإيجاد الحد الأدنى لعدد التخفيضات. نظرًا لأن الحلقة الخارجية تمتد على طول السلسلة الكاملة وأن الحلقة الداخلية تمتد من 0 إلى i-1.

وبالتالي ، جعل وقت التشغيل إجمالي O (N ^ 2).

تعقيد الفضاء: O (N ^ 2)

على الرغم من أن صفيف القطع لدينا الآن أحادي البعد ، إلا أن isPalindrome الخاص بنا لا يزال مصفوفة ثنائية الأبعاد.