logo

TechCodeview

Numărul minim de anexe necesare pentru a face un palindrom de șir

Având în vedere a șir s sarcina este de a găsi minim personaje să fie anexat (inserție la sfârșit) a face un palindrom de coarda. 

Exemple:  

Intrare : s = „terminat”
Ieșire : 2
Explicaţie: Putem face palindrom cu coarde ca 'abede nu ' prin adăugarea nu la capătul sforii.

Intrare :s = 'aabb'
Ieșire : 2
Explicaţie: Putem face palindrom cu coarde as'aabb aa ' prin adăugarea aa la capătul sforii.



Cuprins

Verificați palindromul de fiecare dată - O(n^2) Timp și O(n) Spațiu

Soluția presupune progresiv eliminarea caracterelor din început de sfoară unul câte unul până când sfoara devine a palindrom . Răspunsul va fi numărul total de caractere eliminate.

De exemplu, luați în considerare șirul s = ‘aici’. Mai întâi verificăm dacă întregul șir este un palindrom, ceea ce nu este. Apoi eliminăm primul caracter care rezultă în șir „cerși”. Verificăm din nou, dar încă nu este un palindrom. Apoi eliminăm un alt personaj de la început lăsând „ede”. De data aceasta coarda este un palindrom. Prin urmare, ieșirea este 2 reprezentând numărul de caractere eliminate de la început pentru realizarea unui palindrom.

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);

Ieșire 
2

Folosind algoritmul Knuth Morris Pratt - O(n) timp și O(n) spațiu

Ideea de bază din spatele abordării este că noi calcula cel cel mai mare subșir de la sfârșit si lungimea sforii minus această valoare este minim numărul de anexe. Logica este intuitivă, nu trebuie să anexăm palindrom şi numai cele care nu formează palindromul. Pentru a găsi acest cel mai mare palindrom de la sfârșit am verso șirul calculează DFA.

The DFA (Automat finit determinist) menţionate în contextul Algoritmul Knuth Morris Pratt este un concept folosit pentru a ajuta la găsirea cel mai lung prefix al unui șir care este și sufix și inversați din nou șirul (căstigând astfel înapoi șirul original) și găsiți starea finală care reprezintă numărul de potriviri ale șirului cu șirul venerat și, prin urmare, obținem cel mai mare subșir care este un palindrom de la sfârșit.

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));

Ieșire 
2

  Articol înrudit: 

  • Programare dinamică | Setul 28 (inserții minime pentru a forma un palindrom)
Creați un test