أقصر Palindrome


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

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

أقصر Palindrome

مثال

الإدخال: s = abc

الإخراج: 2 (بإضافة c و b في المقدمة سينتج متناظرة cbabc)

الإدخال: ق = أبا

الإخراج: 1 (بإضافة واجهة ستؤدي إلى تماثل العبء)

طريقة بسيطة

خوارزمية

  1. قم بتهيئة سلسلة من الطول L.
  2. قم بإنشاء متغير عدد صحيح لتخزين العدد ومتغير العلم. قم بتهيئة كلا المتغيرين كـ 0.
  3. اجتياز السلسلة عندما يكون طولها أكبر من 0. اجتياز السلسلة وابدأ في مقارنة حرف البداية بالحرف الختامي حتى تصل إلى منتصف السلسلة. إذا كانت السلسلة الحالية متطابقة ، أي أن أحرف البداية هي نفس أحرف النهاية ، فقم بتحديث متغير العلامة كـ 1 وكسر الحلقة.
  4. عدا ذلك ، قم بزيادة متغير العدد بمقدار 1 وإزالة الحرف الأخير من السلسلة.
  5. إذا كان متغير العلم يساوي 1 ، فعدد الطباعة.

برنامج C ++ للعثور على أقصر متماثل

#include<bits/stdc++.h> 
using namespace std; 
  
bool isPalindrome(string s){ 
    int l = s.length(); 
    int j; 
      
    for(int i=0, j=l-1; i<=j; i++, j--){ 
        if(s[i] != s[j]) 
            return false; 
    } 
    return true; 
} 
  
int main(){ 
    string s = "abc"; 
    int count = 0, f = 0; 
      
    while(s.length()>0){ 
        if(isPalindrome(s)){ 
            f = 1; 
             break; 
        } 
        else{ 
            count++; 
            s.erase(s.begin() + s.length() - 1); 
        } 
    } 
      
    if(f) 
        cout<<count; 
}
2

برنامج Java للعثور على أقصر متماثل

class Palindrome{ 
  
    static boolean isPalindrome(String s){ 
        int l = s.length(); 
  
        for(int i=0, j=l-1; i<=j; i++, j--){ 
            if(s.charAt(i) != s.charAt(j)){ 
                return false; 
            } 
        } 
        return true; 
    } 
  
    public static void main(String[] args){ 
        String s = "abc"; 
        int count = 0, f = 0; 
  
        while(s.length() > 0){ 
            if(isPalindrome(s)){ 
                f = 1; 
                break; 
            } 
            else{ 
                count++; 
  
                s = s.substring(0, s.length() - 1); 
            } 
        } 
  
        if(f == 1){ 
            System.out.println(count); 
        } 
    } 
}
2

تحليل التعقيد

تعقيد الوقت: O (L * L) (L طول السلسلة)

مساحة إضافية: O (1) لأننا استخدمنا مساحة إضافية ثابتة

طريقة فعالة

خوارزمية

  1. قم بتهيئة سلسلة من الطول L.
  2. قم بإنشاء متغير سلسلة وتخزين عكس السلسلة الأصلية فيه.
  3. أنشئ سلسلة أخرى لتخزين تسلسل السلاسل وتخزين تسلسل السلسلة الأصلية والسلسلة المعكوسة بحرف خاص بينهما.
  4. تهيئة صفيف lps.
  5. اجتياز السلسلة وتحديث قيم المصفوفة lps.
  6. قم بإرجاع مجموعة lps.

برنامج C ++ للعثور على أقصر متماثل

#include <bits/stdc++.h> 
using namespace std; 
  
vector<int> computeLPSArray(string s){ 
    int l = s.length(); 
    vector<int> lps(l); 
  
    int len = 0; 
    lps[0] = 0; 
  
    int i = 1; 
    while(i<l){ 
        if(s[i] == s[len]){ 
            len++; 
            lps[i] = len; 
            i++; 
        } 
        else{ 
            if(len != 0){ 
                len = lps[len-1]; 
            } 
            else{ 
                lps[i] = 0; 
                i++; 
            } 
        } 
    } 
    return lps; 
} 
  
int minChar(string s){ 
    string rev = s; 
    reverse(rev.begin(), rev.end()); 
  
    string concat = s + "$" + rev; 
  
    vector<int> lps = computeLPSArray(concat); 
  
    return(s.length() - lps.back()); 
} 
  
int main(){ 
    string s = "abc"; 
    cout<<minChar(s); 
    return 0; 
}
2

برنامج Java للعثور على أقصر متماثل

class Palindrome{ 
  
    public static int[] computeLPSArray(String s){ 
        int l = s.length(); 
        int lps[] = new int[l]; 
        int i = 1, len = 0; 
        lps[0] = 0;
          
        while(i < l){ 
            if(s.charAt(i) == s.charAt(len)){ 
                len++; 
                lps[i] = len; 
                i++; 
            } 
            else{ 
                if(len != 0){ 
                    len = lps[len - 1]; 
                } 
                else{ 
                    lps[i] = 0; 
                    i++; 
                } 
            } 
        } 
        return lps; 
    } 
      
    static int minChar(String s){  
        StringBuilder S = new StringBuilder(); 
        S.append(s); 
          
        String rev = S.reverse().toString(); 
        S.reverse().append("$").append(rev); 
          
        int lps[] = computeLPSArray(S.toString()); 
        return s.length() - lps[S.length() - 1]; 
    } 

    public static void main(String[] args){ 
        String s = "abc"; 
        System.out.println(minChar(s)); 
    } 
}
2

تحليل التعقيد

تعقيد الوقت: O (L) (L هو طول السلسلة)

مساحة إضافية: O (L) لأننا استخدمنا مساحة إضافية للأحرف L.

المراجع