Най-краткият палиндром


Ниво на трудност Трудно
Често задавани в Амазонка Делхейвъри FactSet
Низ

В най-краткия проблем с палиндрома ние дадохме a низ s дължина l. Добавете символи пред него, за да го направите палиндром, ако не е. Отпечатайте най-малкия брой символи, използвани, за да направите дадения низ палиндром.

Най-краткият палиндром

Пример

Вход: s = abc

Изход: 2 (чрез добавяне на c и b отпред ще доведе до палиндром cbabc)

Вход: s = abbaa

Изход: 1 (чрез добавяне на предница ще се получи палиндром aabbaa)

Прост метод

алгоритъм

  1. Инициализирайте низ s дължина L.
  2. Създайте целочислена променлива, за да съхраните променливата count и flag. Инициализирайте и двете променливи като 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. Инициализирайте низ s дължина 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 символи.

Препратки