logo

TechCodeview

Minimum antall vedlegg som trengs for å lage et strengpalindrom

Gitt en streng s oppgaven er å finne minimum karakterer å være vedlagt (innsetting på slutten) å lage et strengpalindrom. 

Eksempler:  

Inndata : s = "ferdig"
Produksjon : 2
Forklaring: Vi kan lage strengpalindrom som 'abede' ikke ' ved å legge til ikke på slutten av strengen.

Inndata :s = 'aabb'
Produksjon : 2
Forklaring: Vi kan lage string palindrome as'aabb aa ' ved å legge til aa på slutten av strengen.



Innholdsfortegnelse

Sjekk palindrom hver gang - O(n^2) Tid og O(n) Mellomrom

Løsningen innebærer progressivt fjerning av tegn fra begynnelse av strengen en etter en til strengen blir en palindrom . Svaret vil være totalt antall tegn fjernet.

Tenk for eksempel på strengen s = ‘her’. Vi sjekker først om hele strengen er et palindrom som den ikke er. Deretter fjerner vi det første tegnet som resulterer i streng 'tigge'. Vi sjekker igjen, men det er fortsatt ikke et palindrom. Vi fjerner så en annen karakter fra starten forlater 'ede'. Denne gangen er strengen et palindrom. Derfor utgang er 2 som representerer antall tegn fjernet fra begynnelsen for å oppnå et 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);

Produksjon 
2

Bruke Knuth Morris Pratt-algoritmen - O(n) tid og O(n) rom

Grunntanken bak tilnærmingen er at vi kalkulere de største delstreng fra slutten og lengden på strengen minus denne verdien er minimum antall vedlegg. Logikken er intuitiv, vi trenger ikke legge til palindrom og bare de som ikke danner palindrom. For å finne dette største palindromet fra slutten vi omvendt strengen beregne DFA.

De DFA (Deterministic Finite Automaton) nevnt i sammenheng med Knuth Morris Pratt Algoritme er et konsept som brukes for å finne lengste prefiks til en streng som også er et suffiks og snu strengen igjen (og dermed få tilbake den opprinnelige strengen) og finn den endelige tilstanden som representerer antall treff av strengen med den ærverdige strengen, og dermed får vi den største understrengen som er et palindrom fra slutten.

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

Produksjon 
2

  Relatert artikkel: 

  • Dynamisk programmering | Sett 28 (Minimum innsettinger for å danne et palindrom)
Lag quiz