資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C 語言程式：查詢形成迴文串的最小插入次數
迴文串是指與自身反轉後相等的字串。給定一個字串，我們需要找到使該字串成為迴文串所需的最小字元插入次數。我們將看到三種方法：首先是遞迴方法，然後我們將記住此解決方案，最後我們將實現動態規劃方法。
遞迴方法
示例
#include <stdio.h> // library for input and output
#include <limits.h> // library to get the integer limits
#include <string.h> // library for strings
// function to find the minimum of two number
// as it is not present in the c language
int findMin(int a, int b){
if(a < b){
return a;
} else{
return b;
}
}
// creating the function to find the required answer we will make recursive calls to it
int findAns(char str[], int start, int end){
// base condition
if (start > end){
return INT_MAX;
}
else if(start == end){
return 0;
}
else if (start == end - 1){
if(str[start] == str[end]){
return 0;
}
else return 1;
}
// check if both start and end characters are the same make callson the basis of that
if(str[start] == str[end]){
return findAns(str,start+1, end-1);
} else{
return 1+ findMin(findAns(str,start,end-1), findAns(str,start+1,end));
}
}
// main function
int main(){
char str[] = "thisisthestring"; // given string
printf("The minimum number of insertions required to form the palindrome is: %d", findAns(str,0,strlen(str)-1));
return 0;
}
輸出
The minimum number of insertions required to form the palindrome is: 8
時間和空間複雜度
以上程式碼的時間複雜度為 O(2^N)，因為我們對每次插入都做出了選擇，其中 N 是給定字串的大小。
以上程式碼的空間複雜度為 O(N)，用於遞迴呼叫。
記憶化方法
示例
#include <stdio.h> // library for input and output
#include <limits.h> // library to get the integer limits
#include <string.h> // library for strings
int memo[1005][1005]; // array to store the recursion results
// function to find the minimum of two number
// as it is not present in the c language
int findMin(int a, int b){
if(a < b){
return a;
} else{
return b;
}
}
// creating the function to find the required answer we will make recursive calls to it
int findAns(char str[], int start, int end){
// base condition
if (start > end){
return INT_MAX;
}
else if(start == end){
return 0;
}
else if (start == end - 1){
if(str[start] == str[end]){
return 0;
}
else return 1;
}
// if already have the result
if(memo[start][end] != -1){
return memo[start][end];
}
// check if both start and end characters are same make calls on basis of that
if(str[start] == str[end]){
memo[start][end] = findAns(str,start+1, end-1);
} else{
memo[start][end] = 1+ findMin(findAns(str,start,end-1), findAns(str,start+1,end));
}
return memo[start][end];
}
int main(){
char str[] = "thisisthestring"; // given string
//Initializing the memo array
memset(memo,-1,sizeof(memo));
printf("The minimum number of insertions required to form the palindrome is: %d", findAns(str,0,strlen(str)-1));
return 0;
}
輸出
The minimum number of insertions required to form the palindrome is: 8
時間和空間複雜度
以上程式碼的時間複雜度為 O(N^2)，因為我們儲存了已經計算的結果。
以上程式碼的空間複雜度為 O(N^2)，因為我們在這裡使用了額外的空間。
動態規劃方法
示例
#include <stdio.h> // library for input and output
#include <limits.h> // library to get the integer limits
#include <string.h> // library for strings
// function to find the minimum of two number
// as it is not present in the c language
int findMin(int a, int b){
if(a < b){
return a;
} else{
return b;
}
}
// creating a function to find the required answer
int findAns(char str[], int len){
// creating the table and initialzing it
int memo[1005][1005];
memset(memo,0,sizeof(memo));
// filling the table by traversing over the string
for (int i = 1; i < len; i++){
for (int start= 0, end = i; end < len; start++, end++){
if(str[start] == str[end]){
memo[start][end] = memo[start+1][end-1];
} else{
memo[start][end] = 1 + findMin(memo[start][end-1], memo[start+1][end]);
}
}
}
// return the minimum numbers of interstion required for the complete string
return memo[0][len-1];
}
int main(){
char str[] = "thisisthestring"; // given string
// calling to the function
printf("The minimum number of insertions required to form the palindrome is: %d", findAns(str, strlen(str)));
return 0;
}
輸出
The minimum number of insertions required to form the palindrome is: 8
時間和空間複雜度
以上程式碼的時間複雜度為 O(N^2)，因為我們在這裡使用了巢狀迴圈。
以上程式碼的空間複雜度為 O(N^2)，因為我們在這裡使用了額外的空間。
結論
在本教程中，我們實現了三種方法來查詢使給定字串成為迴文串所需的最小插入次數。我們實現了遞迴方法，然後對其進行了記憶化。最後，我們實現了表格化方法或動態規劃方法。
更新於： 2023年7月11日
327 次檢視
廣告