算法_Longest Palindromic Substring（寻找最长回文字串）

题目：Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

题解：首先需要清楚什么是“回文“（不知道这个翻译对不对？）字符串！回文字符串关于某一个字符对称，在左右两边与中心相同距离的字符相等。

那么还需要注意的是对称中心可以有多个相同的字符组成，如下图：

 

 

所以编程实现时可以先从对称中心入手，从字符串位置0开始作为对称中心依次验证。时间复杂度O（n²）;

char* longestPalindrome(char* s) {int len=strlen(s);int begin=0,maxlen=0;for(int i=0;i<len;i++){int left=i,right=i;while(right<len-1 && s[right]==s[right+1])right++;while(left>0 && right<len-1 && s[left-1]==s[right+1]){left--;right++;}if((right-left+1)>maxlen){maxlen=right-left+1;begin=left;}}char* s_out=malloc((maxlen+1)*sizeof(char));for(int i=0;i<maxlen;i++){s_out[i]=s[begin++];}s_out[maxlen]='\0';return s_out; }

 

转载于:https://www.cnblogs.com/cwq2014/p/5324488.html

总结

以上是生活随笔为你收集整理的算法_Longest Palindromic Substring（寻找最长回文字串）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。