logo

TechCodeview

Numero minimo di aggiunte necessarie per creare una stringa palindroma

Dato un stringa s il compito è trovare il minimo personaggi da essere aggiunto (inserimento alla fine) per creare un palindromo di stringa. 

Esempi:  

Ingresso : s = "fatto"
Produzione : 2
Spiegazione: Possiamo rendere palindromo la stringa come 'abede non ' aggiungendo non alla fine della corda.

Ingresso :s = 'aabb'
Produzione : 2
Spiegazione: Possiamo rendere palindromo la stringa come'aabb aa ' aggiungendo aa alla fine della corda.



Sommario

Controlla il palindromo ogni volta: O (n ^ 2) Tempo e O (n) Spazio

La soluzione implica progressivamente rimuovendo caratteri da inizio della stringa uno per uno fino a quando la stringa diventa a palindromo . La risposta sarà il numero totale di caratteri rimossi.

Consideriamo ad esempio la stringa s = "qui". Per prima cosa controlliamo se l'intera stringa è palindroma, cosa che non è. Successivamente rimuoviamo il primo carattere risultante in stringa 'beg'. Controlliamo di nuovo ma non è ancora un palindromo. Quindi rimuoviamo un altro carattere dall'inizio lasciando 'ede'. Questa volta la stringa è palindromo. Pertanto il l'uscita è 2 che rappresenta il numero di caratteri rimossi dall'inizio per ottenere un palindromo.

C++ 
// C++ code to find minimum number  // of appends to make string Palindrome #include    using namespace std; // Function to check if a given string is a palindrome bool isPalindrome(string s) {  int left = 0 right = s.length() - 1;  while (left < right) {  if (s[left] != s[right]) return false;  left++;  right--;  }  return true; } // Function to find the minimum number of  // characters to remove from the beginning int noOfAppends(string& s) {  int n = s.length();    // Remove characters from the start until   // the string becomes a palindrome  for (int i = 0; i < n; i++) {  if (isPalindrome(s.substr(i))) {    // Return the number of characters removed  return i;   }  }    // If no palindrome is found remove  // all but one character  return n - 1;  } int main() {  string s = 'abede';  int result = noOfAppends(s);  cout << result << endl;  return 0; }
Java 
// Java code to find minimum number  // of appends to make string Palindrome import java.util.*; class GfG {    // Function to check if a given string is a palindrome  static boolean isPalindrome(String s) {  int left = 0 right = s.length() - 1;  while (left < right) {  if (s.charAt(left) != s.charAt(right)) return false;  left++;  right--;  }  return true;  }    // Function to find the minimum number of   // characters to remove from the beginning  static int noOfAppends(String s) {  int n = s.length();    // Remove characters from the start until   // the string becomes a palindrome  for (int i = 0; i < n; i++) {  if (isPalindrome(s.substring(i))) {    // Return the number of characters removed  return i;  }  }    // If no palindrome is found remove  // all but one character  return n - 1;  }  public static void main(String[] args) {  String s = 'abede';  int result = noOfAppends(s);  System.out.println(result);  } }
Python 
# Python code to find minimum number  # of appends to make string Palindrome # Function to check if a given string is a palindrome def is_palindrome(s): left right = 0 len(s) - 1 while left < right: if s[left] != s[right]: return False left += 1 right -= 1 return True # Function to find the minimum number of  # characters to remove from the beginning def no_of_appends(s): n = len(s) # Remove characters from the start until  # the string becomes a palindrome for i in range(n): if is_palindrome(s[i:]): # Return the number of characters # removed return i # If no palindrome is found remove # all but one character return n - 1 if __name__ == '__main__': s = 'abede' result = no_of_appends(s) print(result)
C# 
// C# code to find minimum number  // of appends to make string Palindrome using System; class GfG {    // Function to check if a given string   // is a palindrome  static bool IsPalindrome(string s) {  int left = 0 right = s.Length - 1;  while (left < right) {  if (s[left] != s[right]) return false;  left++;  right--;  }  return true;  }  // Function to find the minimum number of   // characters to remove from the beginning  static int NoOfAppends(string s) {  int n = s.Length;    // Remove characters from the start until   // the string becomes a palindrome  for (int i = 0; i < n; i++) {  if (IsPalindrome(s.Substring(i))) {    // Return the number of characters  // removed  return i;  }  }    // If no palindrome is found remove all but   // one character  return n - 1;  }  static void Main(string[] args) {  string s = 'abede';  int result = NoOfAppends(s);  Console.WriteLine(result);  } }
JavaScript 
// JavaScript code to find minimum number  // of appends to make string Palindrome // Function to check if a given string is a palindrome function isPalindrome(s) {  let left = 0 right = s.length - 1;  while (left < right) {  if (s[left] !== s[right]) return false;  left++;  right--;  }  return true; } // Function to find the minimum number of  // characters to remove from the beginning function noOfAppends(s) {  let n = s.length;    // Remove characters from the start until   // the string becomes a palindrome  for (let i = 0; i < n; i++) {  if (isPalindrome(s.substring(i))) {    // Return the number of  // characters removed  return i;  }  }    // If no palindrome is found remove  // all but one character  return n - 1; } const s = 'abede'; const result = noOfAppends(s); console.log(result);

Produzione 
2

Utilizzo dell'algoritmo di Knuth Morris Pratt: tempo O(n) e spazio O(n).

L'idea di base alla base dell'approccio è che noi calcolare IL sottostringa più grande dalla fine e la lunghezza della corda meno questo valore è il minimo numero di aggiunte. La logica è intuitiva, non è necessario aggiungere il file palindromo e solo quelli che non formano il palindromo. Per trovare questo palindromo più grande dalla fine noi inversione la stringa calcola il DFAE.

IL DFA (automa finito deterministico) menzionato nel contesto della Algoritmo di Knuth Morris Pratt è un concetto utilizzato per aiutare a trovare il prefisso più lungo di una stringa che è anche un suffisso e invertiamo nuovamente la stringa (recuperando così la stringa originale) e troviamo lo stato finale che rappresenta il numero di corrispondenze della stringa con la stringa venerata e quindi otteniamo la sottostringa più grande che è palindroma dalla fine.

C++ 
// CPP program for the given approach  // using 2D vector for DFA #include    using namespace std; // Function to build the DFA and precompute the state vector<vector<int>> buildDFA(string& s) {  int n = s.length();    // Number of possible characters (ASCII range)  int c = 256;     // Initialize 2D vector with zeros  vector<vector<int>> dfa(n vector<int>(c 0));   int x = 0;  dfa[0][s[0]] = 1;  // Build the DFA for the given string  for (int i = 1; i < n; i++) {  for (int j = 0; j < c; j++) {  dfa[i][j] = dfa[x][j];  }  dfa[i][s[i]] = i + 1;  x = dfa[x][s[i]];  }  return dfa; } // Function to find the longest overlap // between the string and its reverse int longestOverlap(vector<vector<int>>& dfa string& query) {  int ql = query.length();  int state = 0;  // Traverse through the query to   // find the longest overlap  for (int i = 0; i < ql; i++) {  state = dfa[state][query[i]];  }  return state; } // Function to find the minimum // number of characters to append int minAppends(string s) {    // Reverse the string  string reversedS = s;  reverse(reversedS.begin() reversedS.end());  // Build the DFA for the reversed string  vector<vector<int>> dfa = buildDFA(reversedS);  // Get the longest overlap with the original string  int longestOverlapLength = longestOverlap(dfa s);  // Minimum characters to append   // to make the string a palindrome  return s.length() - longestOverlapLength; } int main() {  string s = 'abede';  cout << minAppends(s) << endl;  return 0; }
Java 
// Java program for the given approach // using 2D array for DFA import java.util.*; class GfG {  // Function to build the DFA and precompute the state  static int[][] buildDFA(String s) {  int n = s.length();  // Number of possible characters (ASCII range)  int c = 256;  // Initialize 2D array with zeros  int[][] dfa = new int[n][c];  int x = 0;  dfa[0][s.charAt(0)] = 1;  // Build the DFA for the given string  for (int i = 1; i < n; i++) {  for (int j = 0; j < c; j++) {  dfa[i][j] = dfa[x][j];  }  dfa[i][s.charAt(i)] = i + 1;  x = dfa[x][s.charAt(i)];  }  return dfa;  }  // Function to find the longest overlap  // between the string and its reverse  static int longestOverlap(int[][] dfa String query) {  int ql = query.length();  int state = 0;  // Traverse through the query to   // find the longest overlap  for (int i = 0; i < ql; i++) {  state = dfa[state][query.charAt(i)];  }  return state;  }  // Function to find the minimum  // number of characters to append  static int minAppends(String s) {    // Reverse the string  String reversedS = new StringBuilder(s).reverse().toString();  // Build the DFA for the reversed string  int[][] dfa = buildDFA(reversedS);  // Get the longest overlap with the original string  int longestOverlapLength = longestOverlap(dfa s);  // Minimum characters to append   // to make the string a palindrome  return s.length() - longestOverlapLength;  }  public static void main(String[] args) {  String s = 'abede';  System.out.println(minAppends(s));  } }
Python 
# Python program for the given approach  # using 2D list for DFA # Function to build the DFA and precompute the state def buildDFA(s): n = len(s) # Number of possible characters (ASCII range) c = 256 # Initialize 2D list with zeros dfa = [[0] * c for _ in range(n)] x = 0 dfa[0][ord(s[0])] = 1 # Build the DFA for the given string for i in range(1 n): for j in range(c): dfa[i][j] = dfa[x][j] dfa[i][ord(s[i])] = i + 1 x = dfa[x][ord(s[i])] return dfa # Function to find the longest overlap # between the string and its reverse def longestOverlap(dfa query): ql = len(query) state = 0 # Traverse through the query to  # find the longest overlap for i in range(ql): state = dfa[state][ord(query[i])] return state # Function to find the minimum # number of characters to append def minAppends(s): # Reverse the string reversedS = s[::-1] # Build the DFA for the reversed string dfa = buildDFA(reversedS) # Get the longest overlap with the # original string longestOverlapLength = longestOverlap(dfa s) # Minimum characters to append  # to make the string a palindrome return len(s) - longestOverlapLength if __name__ == '__main__': s = 'abede' print(minAppends(s))
C# 
// C# program for the given approach // using 2D array for DFA using System; class GfG {  // Function to build the DFA and precompute the state  static int[] buildDFA(string s) {  int n = s.Length;  // Number of possible characters   // (ASCII range)  int c = 256;  // Initialize 2D array with zeros  int[] dfa = new int[n c];  int x = 0;  dfa[0 s[0]] = 1;  // Build the DFA for the given string  for (int i = 1; i < n; i++) {  for (int j = 0; j < c; j++) {  dfa[i j] = dfa[x j];  }  dfa[i s[i]] = i + 1;  x = dfa[x s[i]];  }  return dfa;  }  // Function to find the longest overlap  // between the string and its reverse  static int longestOverlap(int[] dfa string query) {  int ql = query.Length;  int state = 0;  // Traverse through the query to   // find the longest overlap  for (int i = 0; i < ql; i++) {  state = dfa[state query[i]];  }  return state;  }  // Function to find the minimum  // number of characters to append  static int minAppends(string s) {    // Reverse the string using char array  char[] reversedArray = s.ToCharArray();  Array.Reverse(reversedArray);  string reversedS = new string(reversedArray);  // Build the DFA for the reversed string  int[] dfa = buildDFA(reversedS);  // Get the longest overlap with the original string  int longestOverlapLength = longestOverlap(dfa s);  // Minimum characters to append   // to make the string a palindrome  return s.Length - longestOverlapLength;  }  static void Main() {  string s = 'abede';  Console.WriteLine(minAppends(s));  } }
JavaScript 
// JavaScript program for the given approach // using 2D array for DFA // Function to build the DFA and precompute the state function buildDFA(s) {  let n = s.length;  // Number of possible characters  // (ASCII range)  let c = 256;  // Initialize 2D array with zeros  let dfa = Array.from({ length: n } () => Array(c).fill(0));  let x = 0;  dfa[0][s.charCodeAt(0)] = 1;  // Build the DFA for the given string  for (let i = 1; i < n; i++) {  for (let j = 0; j < c; j++) {  dfa[i][j] = dfa[x][j];  }  dfa[i][s.charCodeAt(i)] = i + 1;  x = dfa[x][s.charCodeAt(i)];  }  return dfa; } // Function to find the longest overlap // between the string and its reverse function longestOverlap(dfa query) {  let ql = query.length;  let state = 0;  // Traverse through the query to   // find the longest overlap  for (let i = 0; i < ql; i++) {  state = dfa[state][query.charCodeAt(i)];  }  return state; } // Function to find the minimum // number of characters to append function minAppends(s) {  // Reverse the string  let reversedS = s.split('').reverse().join('');  // Build the DFA for the reversed string  let dfa = buildDFA(reversedS);  // Get the longest overlap with the original string  let longestOverlapLength = longestOverlap(dfa s);  // Minimum characters to append   // to make the string a palindrome  return s.length - longestOverlapLength; } let s = 'abede'; console.log(minAppends(s));

Produzione 
2

  Articolo correlato: 

  • Programmazione dinamica | Set 28 (Inserzioni minime per formare un palindromo)
Crea quiz