Gegeven een string s die alleen uit kleine Engelse letters bestaat, zoek dan de minimum aantal tekens dat moet zijn toegevoegd naar de voorkant van s om er een palindroom van te maken.
Opmerking: Een palindroom is een string die voorwaarts en achterwaarts hetzelfde leest.
string.vergelijk c#
Voorbeelden:
Invoer : s = 'abc'
Uitvoer : 2
Uitleg : We kunnen het bovenstaande stringpalindroom maken als 'cbabc' door 'b' en 'c' aan de voorkant toe te voegen.Invoer : s = 'aacecaaaa'
Uitvoer : 2
Uitleg : We kunnen het palindroom hierboven maken als 'aaaacecaaaa' door twee a's toe te voegen aan de voorkant van de string.
Inhoudsopgave
- [Naïeve aanpak] Alle voorvoegsels controleren - O(n^2) Tijd en O(1) Ruimte
- [Verwachte aanpak 1] Met behulp van lps-array van KMP-algoritme - O(n) tijd en O(n) ruimte
- [Verwachte aanpak 2] Het algoritme van Manacher gebruiken
[Naïeve aanpak] Alle voorvoegsels controleren - O(n^2) Tijd en O(1) Ruimte
Het idee is gebaseerd op de observatie dat we het langste voorvoegsel uit een gegeven string moeten vinden, wat ook een palindroom is. Het minimum aantal voortekens dat moet worden toegevoegd om een gegeven stringpalindroom te maken, zijn dan de resterende tekens.
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));
Uitvoer
2
[Verwachte aanpak 1] Met behulp van lps-array van KMP-algoritme - O(n) tijd en O(n) ruimte
De belangrijkste observatie is dat het langste palindroomvoorvoegsel van een string het langste palindroomachtervoegsel van het omgekeerde wordt.
Gegeven een string s = 'aacecaaaa' is het omgekeerde revS = 'aaaacecaa'. Het langste palindroomvoorvoegsel van s is 'aacecaa'.
Om dit efficiënt te vinden, gebruiken we de LPS-array uit de KMP-algoritme . We voegen de originele string samen met een speciaal teken en het omgekeerde ervan: s + '$' + revS.
De LPS-array voor deze gecombineerde reeks helpt bij het identificeren van het langste voorvoegsel van s dat overeenkomt met een achtervoegsel van revS dat ook het palindroomvoorvoegsel van s vertegenwoordigt.
De laatste waarde van de LPS-array vertelt ons hoeveel tekens in het begin al een palindroom vormen. Het minimumaantal tekens dat moet worden toegevoegd om van s een palindroom te maken, is dus 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));
Uitvoer
2
[Verwachte aanpak 2] Het algoritme van Manacher gebruiken
C++Het idee is om te gebruiken Het algoritme van Manager om efficiënt alle palindrome substrings in lineaire tijd te vinden.
We transformeren de string door speciale tekens (#) in te voegen om zowel palindromen met even als oneven lengte uniform te verwerken.
Na de voorbewerking scannen we vanaf het einde van de originele string en gebruiken we de palindroomradiusarray om te controleren of het voorvoegsel s[0...i] een palindroom is. De eerste dergelijke index i geeft ons het langste palindroomvoorvoegsel en we retourneren n - (i + 1) als het minimum aantal tekens dat moet worden toegevoegd.
#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));
Uitvoer
2
Tijdcomplexiteit: Het algoritme van O(n) manacher werkt in lineaire tijd door palindromen in elk centrum uit te breiden zonder karakters opnieuw te bezoeken, en de prefix-controlelus voert O(1)-bewerkingen uit per karakter over n karakters.
Hulpruimte: O(n) gebruikt voor de gewijzigde string en de palindroomlengtearray p[] die beide lineair groeien met de invoergrootte.