Data una stringa s composta solo da lettere inglesi minuscole, trova the minimo numero di caratteri che devono essere aggiunto al anteriore di s per renderlo palindromo.
Nota: Un palindromo è una stringa che si legge allo stesso modo sia in avanti che all'indietro.
Esempi:
Ingresso : s = 'abc'
Produzione : 2
Spiegazione : Possiamo rendere palindromo la stringa sopra come 'cbabc' aggiungendo 'b' e 'c' all'inizio.Ingresso : s = 'aacecaaaa'
Produzione : 2
Spiegazione : Possiamo rendere palindromo la stringa sopra come 'aaaacecaaaa' aggiungendo due a davanti alla stringa.
Sommario
- [Approccio ingenuo] Controllo di tutti i prefissi: O(n^2) Tempo e O(1) Spazio
- [Approccio previsto 1] Utilizzo dell'array lps dell'algoritmo KMP - O(n) Tempo e O(n) Spazio
- [Approccio previsto 2] Utilizzo dell'algoritmo di Manacher
[Approccio ingenuo] Controllo di tutti i prefissi: O(n^2) Tempo e O(1) Spazio
L'idea si basa sull'osservazione che dobbiamo trovare il prefisso più lungo da una determinata stringa che è anche palindromo. Quindi i caratteri iniziali minimi da aggiungere per rendere palindromo la stringa data saranno i caratteri rimanenti.
C++ #include
#include
class GfG { // function to check if the substring // s[i...j] is a palindrome static boolean isPalindrome(String s int i int j) { while (i < j) { // if characters at the ends are not the same // it's not a palindrome if (s.charAt(i) != s.charAt(j)) { return false; } i++; j--; } return true; } static int minChar(String s) { int cnt = 0; int i = s.length() - 1; // iterate from the end of the string checking for the // longest palindrome starting from the beginning while (i >= 0 && !isPalindrome(s 0 i)) { i--; cnt++; } return cnt; } public static void main(String[] args) { String s = 'aacecaaaa'; System.out.println(minChar(s)); } }
# function to check if the substring s[i...j] is a palindrome def isPalindrome(s i j): while i < j: # if characters at the ends are not the same # it's not a palindrome if s[i] != s[j]: return False i += 1 j -= 1 return True def minChar(s): cnt = 0 i = len(s) - 1 # iterate from the end of the string checking for the # longest palindrome starting from the beginning while i >= 0 and not isPalindrome(s 0 i): i -= 1 cnt += 1 return cnt if __name__ == '__main__': s = 'aacecaaaa' print(minChar(s))
using System; class GfG { // function to check if the substring s[i...j] is a palindrome static bool isPalindrome(string s int i int j) { while (i < j) { // if characters at the ends are not the same // it's not a palindrome if (s[i] != s[j]) { return false; } i++; j--; } return true; } static int minChar(string s) { int cnt = 0; int i = s.Length - 1; // iterate from the end of the string checking for the longest // palindrome starting from the beginning while (i >= 0 && !isPalindrome(s 0 i)) { i--; cnt++; } return cnt; } static void Main() { string s = 'aacecaaaa'; Console.WriteLine(minChar(s)); } }
// function to check if the substring s[i...j] is a palindrome function isPalindrome(s i j) { while (i < j) { // if characters at the ends are not the same // it's not a palindrome if (s[i] !== s[j]) { return false; } i++; j--; } return true; } function minChar(s) { let cnt = 0; let i = s.length - 1; // iterate from the end of the string checking for the // longest palindrome starting from the beginning while (i >= 0 && !isPalindrome(s 0 i)) { i--; cnt++; } return cnt; } // Driver code let s = 'aacecaaaa'; console.log(minChar(s));
Produzione
2
[Approccio previsto 1] Utilizzo dell'array lps dell'algoritmo KMP - O(n) Tempo e O(n) Spazio
L'osservazione chiave è che il prefisso palindromico più lungo di una stringa diventa il suffisso palindromico più lungo del suo rovescio.
Data una stringa s = 'aacecaaaa' il suo inverso revS = 'aaaacecaa'. Il prefisso palindromico più lungo della s è 'aacecaa'.
Per trovarlo in modo efficiente utilizziamo l'array LPS da Algoritmo KMP . Concateniamo la stringa originale con un carattere speciale e il suo inverso: s + '$' + revS.
L'array LPS per questa stringa combinata aiuta a identificare il prefisso più lungo di s che corrisponde a un suffisso di revS che rappresenta anche il prefisso palindromico di s.
L'ultimo valore dell'array LPS ci dice quanti caratteri formano già un palindromo all'inizio. Pertanto il numero minimo di caratteri da aggiungere per rendere s un palindromo è s.length() - lps.back().
C++#include
import java.util.ArrayList; class GfG { static int[] computeLPSArray(String pat) { int n = pat.length(); int[] lps = new int[n]; // lps[0] is always 0 lps[0] = 0; int len = 0; // loop calculates lps[i] for i = 1 to n-1 int i = 1; while (i < n) { // if the characters match increment len // and set lps[i] if (pat.charAt(i) == pat.charAt(len)) { len++; lps[i] = len; i++; } // if there is a mismatch else { // if len is not zero update len to // the last known prefix length if (len != 0) { len = lps[len - 1]; } // no prefix matches set lps[i] to 0 else { lps[i] = 0; i++; } } } return lps; } // returns minimum character to be added at // front to make string palindrome static int minChar(String s) { int n = s.length(); String rev = new StringBuilder(s).reverse().toString(); // get concatenation of string special character // and reverse string s = s + '$' + rev; // get LPS array of this concatenated string int[] lps = computeLPSArray(s); // by subtracting last entry of lps array from // string length we will get our result return (n - lps[lps.length - 1]); } public static void main(String[] args) { String s = 'aacecaaaa'; System.out.println(minChar(s)); } }
def computeLPSArray(pat): n = len(pat) lps = [0] * n # lps[0] is always 0 len_lps = 0 # loop calculates lps[i] for i = 1 to n-1 i = 1 while i < n: # if the characters match increment len # and set lps[i] if pat[i] == pat[len_lps]: len_lps += 1 lps[i] = len_lps i += 1 # if there is a mismatch else: # if len is not zero update len to # the last known prefix length if len_lps != 0: len_lps = lps[len_lps - 1] # no prefix matches set lps[i] to 0 else: lps[i] = 0 i += 1 return lps # returns minimum character to be added at # front to make string palindrome def minChar(s): n = len(s) rev = s[::-1] # get concatenation of string special character # and reverse string s = s + '$' + rev # get LPS array of this concatenated string lps = computeLPSArray(s) # by subtracting last entry of lps array from # string length we will get our result return n - lps[-1] if __name__ == '__main__': s = 'aacecaaaa' print(minChar(s))
using System; class GfG { static int[] computeLPSArray(string pat) { int n = pat.Length; int[] lps = new int[n]; // lps[0] is always 0 lps[0] = 0; int len = 0; // loop calculates lps[i] for i = 1 to n-1 int i = 1; while (i < n) { // if the characters match increment len // and set lps[i] if (pat[i] == pat[len]) { len++; lps[i] = len; i++; } // if there is a mismatch else { // if len is not zero update len to // the last known prefix length if (len != 0) { len = lps[len - 1]; } // no prefix matches set lps[i] to 0 else { lps[i] = 0; i++; } } } return lps; } // minimum character to be added at // front to make string palindrome static int minChar(string s) { int n = s.Length; char[] charArray = s.ToCharArray(); Array.Reverse(charArray); string rev = new string(charArray); // get concatenation of string special character // and reverse string s = s + '$' + rev; // get LPS array of this concatenated string int[] lps = computeLPSArray(s); // by subtracting last entry of lps array from // string length we will get our result return n - lps[lps.Length - 1]; } static void Main() { string s = 'aacecaaaa'; Console.WriteLine(minChar(s)); } }
function computeLPSArray(pat) { let n = pat.length; let lps = new Array(n).fill(0); // lps[0] is always 0 let len = 0; // loop calculates lps[i] for i = 1 to n-1 let i = 1; while (i < n) { // if the characters match increment len // and set lps[i] if (pat[i] === pat[len]) { len++; lps[i] = len; i++; } // if there is a mismatch else { // if len is not zero update len to // the last known prefix length if (len !== 0) { len = lps[len - 1]; } // no prefix matches set lps[i] to 0 else { lps[i] = 0; i++; } } } return lps; } // returns minimum character to be added at // front to make string palindrome function minChar(s) { let n = s.length; let rev = s.split('').reverse().join(''); // get concatenation of string special character // and reverse string s = s + '$' + rev; // get LPS array of this concatenated string let lps = computeLPSArray(s); // by subtracting last entry of lps array from // string length we will get our result return n - lps[lps.length - 1]; } // Driver Code let s = 'aacecaaaa'; console.log(minChar(s));
Produzione
2
[Approccio previsto 2] Utilizzo dell'algoritmo di Manacher
C++L'idea è usare Algoritmo di Manacher per trovare in modo efficiente tutte le sottostringhe palindromiche nel tempo lineare.
Trasformiamo la stringa inserendo caratteri speciali (#) per gestire in modo uniforme sia i palindromi di lunghezza pari che quelli dispari.
Dopo la preelaborazione eseguiamo la scansione dalla fine della stringa originale e utilizziamo l'array del raggio palindromo per verificare se il prefisso s[0...i] è palindromo. Il primo di questi indici i ci fornisce il prefisso palindromico più lungo e restituiamo n - (i + 1) come caratteri minimi da aggiungere.
#include
class GfG { // manacher's algorithm for finding longest // palindromic substrings static class manacher { // array to store palindrome lengths centered // at each position int[] p; // modified string with separators and sentinels String ms; manacher(String s) { StringBuilder sb = new StringBuilder('@'); for (char c : s.toCharArray()) { sb.append('#').append(c); } sb.append('#$'); ms = sb.toString(); runManacher(); } // core Manacher's algorithm void runManacher() { int n = ms.length(); p = new int[n]; int l = 0 r = 0; for (int i = 1; i < n - 1; ++i) { if (i < r) p[i] = Math.min(r - i p[r + l - i]); // expand around the current center while (ms.charAt(i + 1 + p[i]) == ms.charAt(i - 1 - p[i])) p[i]++; // update center if palindrome goes beyond // current right boundary if (i + p[i] > r) { l = i - p[i]; r = i + p[i]; } } } // returns the length of the longest palindrome // centered at given position int getLongest(int cen int odd) { int pos = 2 * cen + 2 + (odd == 0 ? 1 : 0); return p[pos]; } // checks whether substring s[l...r] is a palindrome boolean check(int l int r) { int len = r - l + 1; int longest = getLongest((l + r) / 2 len % 2); return len <= longest; } } // returns the minimum number of characters to add at the // front to make the given string a palindrome static int minChar(String s) { int n = s.length(); manacher m = new manacher(s); // scan from the end to find the longest // palindromic prefix for (int i = n - 1; i >= 0; --i) { if (m.check(0 i)) return n - (i + 1); } return n - 1; } public static void main(String[] args) { String s = 'aacecaaaa'; System.out.println(minChar(s)); } }
# manacher's algorithm for finding longest # palindromic substrings class manacher: # array to store palindrome lengths centered # at each position def __init__(self s): # modified string with separators and sentinels self.ms = '@' for c in s: self.ms += '#' + c self.ms += '#$' self.p = [] self.runManacher() # core Manacher's algorithm def runManacher(self): n = len(self.ms) self.p = [0] * n l = r = 0 for i in range(1 n - 1): if i < r: self.p[i] = min(r - i self.p[r + l - i]) # expand around the current center while self.ms[i + 1 + self.p[i]] == self.ms[i - 1 - self.p[i]]: self.p[i] += 1 # update center if palindrome goes beyond # current right boundary if i + self.p[i] > r: l = i - self.p[i] r = i + self.p[i] # returns the length of the longest palindrome # centered at given position def getLongest(self cen odd): pos = 2 * cen + 2 + (0 if odd else 1) return self.p[pos] # checks whether substring s[l...r] is a palindrome def check(self l r): length = r - l + 1 longest = self.getLongest((l + r) // 2 length % 2) return length <= longest # returns the minimum number of characters to add at the # front to make the given string a palindrome def minChar(s): n = len(s) m = manacher(s) # scan from the end to find the longest # palindromic prefix for i in range(n - 1 -1 -1): if m.check(0 i): return n - (i + 1) return n - 1 if __name__ == '__main__': s = 'aacecaaaa' print(minChar(s))
using System; class GfG { // manacher's algorithm for finding longest // palindromic substrings class manacher { // array to store palindrome lengths centered // at each position public int[] p; // modified string with separators and sentinels public string ms; public manacher(string s) { ms = '@'; foreach (char c in s) { ms += '#' + c; } ms += '#$'; runManacher(); } // core Manacher's algorithm void runManacher() { int n = ms.Length; p = new int[n]; int l = 0 r = 0; for (int i = 1; i < n - 1; ++i) { if (i < r) p[i] = Math.Min(r - i p[r + l - i]); // expand around the current center while (ms[i + 1 + p[i]] == ms[i - 1 - p[i]]) p[i]++; // update center if palindrome goes beyond // current right boundary if (i + p[i] > r) { l = i - p[i]; r = i + p[i]; } } } // returns the length of the longest palindrome // centered at given position public int getLongest(int cen int odd) { int pos = 2 * cen + 2 + (odd == 0 ? 1 : 0); return p[pos]; } // checks whether substring s[l...r] is a palindrome public bool check(int l int r) { int len = r - l + 1; int longest = getLongest((l + r) / 2 len % 2); return len <= longest; } } // returns the minimum number of characters to add at the // front to make the given string a palindrome static int minChar(string s) { int n = s.Length; manacher m = new manacher(s); // scan from the end to find the longest // palindromic prefix for (int i = n - 1; i >= 0; --i) { if (m.check(0 i)) return n - (i + 1); } return n - 1; } static void Main() { string s = 'aacecaaaa'; Console.WriteLine(minChar(s)); } }
// manacher's algorithm for finding longest // palindromic substrings class manacher { // array to store palindrome lengths centered // at each position constructor(s) { // modified string with separators and sentinels this.ms = '@'; for (let c of s) { this.ms += '#' + c; } this.ms += '#$'; this.p = []; this.runManacher(); } // core Manacher's algorithm runManacher() { const n = this.ms.length; this.p = new Array(n).fill(0); let l = 0 r = 0; for (let i = 1; i < n - 1; ++i) { if (i < r) this.p[i] = Math.min(r - i this.p[r + l - i]); // expand around the current center while (this.ms[i + 1 + this.p[i]] === this.ms[i - 1 - this.p[i]]) this.p[i]++; // update center if palindrome goes beyond // current right boundary if (i + this.p[i] > r) { l = i - this.p[i]; r = i + this.p[i]; } } } // returns the length of the longest palindrome // centered at given position getLongest(cen odd) { const pos = 2 * cen + 2 + (odd === 0 ? 1 : 0); return this.p[pos]; } // checks whether substring s[l...r] is a palindrome check(l r) { const len = r - l + 1; const longest = this.getLongest(Math.floor((l + r) / 2) len % 2); return len <= longest; } } // returns the minimum number of characters to add at the // front to make the given string a palindrome function minChar(s) { const n = s.length; const m = new manacher(s); // scan from the end to find the longest // palindromic prefix for (let i = n - 1; i >= 0; --i) { if (m.check(0 i)) return n - (i + 1); } return n - 1; } // Driver Code const s = 'aacecaaaa'; console.log(minChar(s));
Produzione
2
Complessità temporale: L'algoritmo di O(n) manacher viene eseguito in tempo lineare espandendo palindromi in ciascun centro senza rivisitare i caratteri e il ciclo di controllo del prefisso esegue operazioni O(1) per carattere su n caratteri.
Spazio ausiliario: O(n) utilizzato per la stringa modificata e l'array palindromo di lunghezza p[], entrambi i quali crescono linearmente con la dimensione dell'input.