原创投稿
广告
广告
广告 广告 广告 广告
广告
广告 国内BGP机房32G内存299元 网站收录排名问题解决 【超牛】搜外友链平台 站长在线扒站工具【免费】 【免费】站长开发工具箱 【推荐】站长自动外链工具 广告位联系QQ：253000106 独立服务器100M/不限/免备 2核2G服务器新用户低至68元/年 虚拟资源平台,轻松变现 10000来路IP只需8元 站群系统程序-专注SEO站群 黑帽SEO论坛_黑帽聚集地 企业HTTP代理IP服务提供商 软文推广，在线获客【定制】 站群服务器99元起 SEO免费工具分享 外推代发包收录 【国内国际】短信推广，免费测试 实力产品收量 外链代发 5分一条 快速排名 █一解决“收录、排名”问题一█ ●●●优质搜狗泛收录域名●●● AI数字人直播系统源码 百度SEO排名7-15天上首页
  1. 创想鸟首页
  2. 站长之家
  3. 编程技术

C程序查找形成回文的最小插入次数

PHP中文网 • • 编程技术 • 阅读 2

c程序查找形成回文的最小插入次数

回文是一个与其反转相等的字符串。给定一个字符串，我们需要找到使该字符串成为回文所需的最小插入任意字符的数量。我们将看到三种方法：首先是递归方法，然后我们将记忆化这个解决方案，最后，我们将实现动态规划方法。

递归方法

示例

#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 
输出
The minimum number of insertions required to form the palindrome is: 8


登录后复制登录后复制


时间和空间复杂度


上述代码的时间复杂度为O(N^2)，因为我们在这里使用了嵌套的for循环。


上述代码的空间复杂度为O(N^2)，因为我们在这里使用了额外的空间。


结论


在本教程中，我们实现了三种方法来找到使给定字符串成为回文所需的最小插入次数。我们实现了递归方法，然后进行了记忆化处理。最后，我们实现了表格法或动态规划法。


以上就是C程序查找形成回文的最小插入次数的详细内容，更多请关注【创想鸟】其它相关文章！





 
 



                                                        
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至253000106@qq.com举报，一经查实，本站将立刻删除。


发布者：PHP中文网，转转请注明出处：https://www.chuangxiangniao.com/p/2583622.html
                        


                        

                        

                            
 赞 (0)

                                                    


                        

                            

                                                                

                                    

                                                                                     0                                         0                                                                            

                                    
                                    

                                        
                                    

                                

                            

                        

                    

                    

    
关于作者
    

        

            PHP中文网的头像
        

        

            

                

                    PHP中文网签约作者
                

                

                                    

            

                            
            

                383.6K
                文章
            

                    

                0
                评论
            

                    

                1
                粉丝
            

        

                        
php中文网提供大量免费、原创、高清的php视频教程，并定期举行公益php培训！可边学习边在线修改示例代码，查看执行效果！php从入门到精通，一站式php自学平台！
        

    


                        

                    

                
                

                     上一篇
                    2025年3月6日 14:36:52
                

            

                            

                
                

                    下一篇 
                    2025年3月1日 01:09:01
                

            

            

                    




AD推荐 黄金广告位招租... 更多推荐









                                            

                            
相关推荐
                        

                    


    	

		
发表回复 
登录后才能评论

请登录

您还未登录，请登录后再进行相关操作！

登录 注册