Ən qısa Palindrom

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon Çatdırılma Məlumat dəsti
SimBaxılıb 47

Ən qısa palindrom problemində bir sim l uzunluq l. Əksinə palindrom etmək üçün önünə simvol əlavə edin. Verilən simli palindrom etmək üçün istifadə olunan ən kiçik simvol sayını çap edin.

Ən qısa PalindromPin

misal

Giriş: s = abc

Çıxış: 2 (önə c və b əlavə etməklə palindrome cbabc ilə nəticələnəcəkdir)

Giriş: s = abbaa

Çıxış: 1 (ön əlavə edərək palindrom aabbaa ilə nəticələnəcək)

Sadə metod

Alqoritm

  1. L uzunluğunda bir s sətri başlayın.
  2. Sayını və bayraq dəyişkənini saxlamaq üçün tam bir dəyişən yaradın. Hər iki dəyişəni 0 olaraq başlayın.
  3. Uzunluq 0-dan çox olduğu halda simdən keçin. Simdən keçin və simlin ortasına çatana qədər başlanğıc simvolunu son xarakterlə müqayisə etməyə başlayın. Mövcud sətir palindromdursa, yəni başlanğıc simvolları son simvollarla eynidirsə, bayraq dəyişənini 1 kimi yeniləyin və dövrəni kəsin.
  4. Başqa bir sayma dəyişənini 1 artırın və sətrin son simvolunu silin.
  5. Bayraq dəyişəni 1-ə bərabərdirsə, sayını çap edin.

Ən qısa palindromu tapmaq üçün C ++ proqramı

#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

Ən qısa palindromu tapmaq üçün Java Proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (L * L) (L simli uzunluqdur)

Köməkçi məkan: O (1), çünki daimi əlavə yer istifadə etdik

Səmərəli metod

Alqoritm

  1. L uzunluğunda bir s sətri başlayın.
  2. Bir simli dəyişən yaradın və orijinal sətrin əksini içində saxlayın.
  3. İplərin birləşdirilməsini saxlamaq və orijinal simli və əks simli aralarında xüsusi bir simvol ilə birləşdirməyi saxlamaq üçün başqa bir simli yaradın.
  4. Bir lps dizisini başlatın.
  5. Sətrdən keçin və lps massivinin dəyərlərini yeniləyin.
  6. Lps dizisini qaytarın.

Ən qısa palindromu tapmaq üçün C ++ proqramı

#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

Ən qısa palindromu tapmaq üçün Java Proqramı

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi: O (L) (L simli uzunluqdur)

Köməkçi məkan: O (L), çünki L simvolları üçün əlavə yer istifadə etdik.

References

Translate »