回文是一个与其反转相等的字符串。给定一个字符串，我们需要找到使该字符串成为回文所需的最小插入任意字符的数量。我们将看到三种方法：首先是递归方法，然后我们将记忆化这个解决方案，最后，我们将实现动态规划方法。
递归方法
示例
#include // library for input and output#include // library to get the integer limits #include // 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 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 // library for input and output#include // library to get the integer limits #include // 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 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 // library for input and output#include // library to get the integer limits #include // 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)，因为我们在这里使用了嵌套的for循环。
上述代码的空间复杂度为O(N^2)，因为我们在这里使用了额外的空间。
结论
在本教程中，我们实现了三种方法来找到使给定字符串成为回文所需的最小插入次数。我们实现了递归方法，然后进行了记忆化处理。最后，我们实现了表格法或动态规划法。
以上就是C程序查找形成回文的最小插入次数的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1444437.html
微信扫一扫 
支付宝扫一扫 
