十年网站开发经验 + 多家企业客户 + 靠谱的建站团队
量身定制 + 运营维护+专业推广+无忧售后,网站问题一站解决
今天就跟大家聊聊有关数据结构中子串该怎么计算,可能很多人都不太了解,为了让大家更加了解,小编给大家总结了以下内容,希望大家根据这篇文章可以有所收获。
在琼山等地区,都构建了全面的区域性战略布局,加强发展的系统性、市场前瞻性、产品创新能力,以专注、极致的服务理念,为客户提供成都网站设计、做网站、成都外贸网站建设公司 网站设计制作定制开发,公司网站建设,企业网站建设,品牌网站设计,网络营销推广,外贸营销网站建设,琼山网站建设费用合理。
“回文串”是一个正读和反读都一样的字符串。
给定一个字符串 s ,找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。
示例 1:
输入: "babad"
输出: "bab"
注意: "aba"也是一个有效答案。
示例 2:
输入: "cbbd"
输出: "bb"
1. Swift 语言
class LongestPalindromicSubstring { func longestPalindrome(_ s: String) -> String { guard s.characters.count > 1 else { return s } var sChars = [Character](s.characters) let len = sChars.count var maxLen = 1 var maxStart = 0 var isPalin = Array(repeating: Array(repeating: false, count : len), count : len) // set palindrome whose len is 1 for i in 0...len - 1 { isPalin[i][i] = true } // set palindrome whose len is 2 for i in 0...len - 2 { if sChars[i] == sChars[i + 1] { isPalin[i][i + 1] = true maxLen = 2 maxStart = i } } if len >= 3 { for length in 3...len { for i in 0...len - length { if sChars[i] == sChars[i + length - 1] && isPalin[i + 1][i + length - 2] { isPalin[i][i + length - 1] = true maxLen = length maxStart = i } } } } return String(sChars[maxStart...maxStart + maxLen - 1]) } }
2. JavaScript 语言
/** * @param {string} s * @return {string} */ // return the Longest Palindromic Substring of s function Manacher(s) { var str = '*#' , dp = [] , maxn = 0 , idx = 0; for (var i = 0, len = s.length; i < len; i++) str += s[i] + '#'; for (var i = 1, len = str.length; i < len; i++) { if (maxn > i) dp[i] = Math.min(dp[2 * idx - i], maxn - i); else dp[i] = 1; while (str[i - dp[i]] === str[i + dp[i]]) dp[i]++; if (dp[i] + i > maxn) maxn = dp[i] + i, idx = i; } var ans = 0 , pos; for (var i = 1; i < len; i++) { if (dp[i] > ans) ans = dp[i], pos = i; } var f = str[pos] === '#' , tmp = f ? '' : str[pos] , startPos = f ? pos + 1 : pos + 2 , endPos = f ? dp[pos] - 3 + startPos : dp[pos] - 4 + startPos; for (var i = startPos; i <= endPos; i += 2) tmp = str[i] + tmp + str[i]; return tmp; } var longestPalindrome = function(s) { var str = Manacher(s); return str; };
3. Python 语言
class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ left = right = 0 n = len(s) for i in range(n - 1): if 2 * (n - i) + 1 < right - left + 1: break l = r = i while l >= 0 and r < n and s[l] == s[r]: l -= 1 r += 1 if r - l - 2 > right - left: left = l + 1 right = r - 1 l = i r = i + 1 while l >= 0 and r < n and s[l] == s[r]: l -= 1 r += 1 if r - l - 2 > right - left: left = l + 1 right = r - 1 return s[left:right + 1]
4. Java 语言
public String longestPalindrome(String s) { if (s == null || s.length() < 1) return ""; int start = 0, end = 0; for (int i = 0; i < s.length(); i++) { int len1 = expandAroundCenter(s, i, i); int len2 = expandAroundCenter(s, i, i + 1); int len = Math.max(len1, len2); if (len > end - start) { start = i - (len - 1) / 2; end = i + len / 2; } } return s.substring(start, end + 1); } private int expandAroundCenter(String s, int left, int right) { int L = left, R = right; while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) { L--; R++; } return R - L - 1; }
5. C++ 语言
#include#include #include #include using namespace std; string findPalindrome(string s, int left, int right) { int n = s.size(); int l = left; int r = right; while (left>=0 && right<=n-1 && s[left] == s[right]) { left--; right++; } return s.substr(left+1, right-left-1); } // This is the common solution. // Actuatlly it's faster than DP solution under Leetcode's test // the below optimized DP solution need 700ms+, this needs around 250ms. string longestPalindrome_recursive_way(string s) { int n = s.size(); if (n<=1) return s; string longest; string str; for (int i=0; i longest.size()){ longest = str; } str = findPalindrome(s, i, i+1); if (str.size() > longest.size()){ longest = str; } } return longest; } //================================================================================ void findPalindrome(string s, int left, int right, int& start, int& len) { int n = s.size(); int l = left; int r = right; while (left>=0 && right<=n-1 && s[left] == s[right]) { left--; right++; } if (right-left-1 > len){ len = right-left-1; start = left+1; } } //The following solution is better than previous solution. //Because it remove the sub-string return in findPalindrome(). string longestPalindrome_recursive_way2(string s) { int n = s.size(); if (n<=1) return s; int start=0, len=0; string longest; string str; for (int i=0; i s[j] is Palindrome or not. //using char or int could cause the `Memory Limit Error` //vector< vector > matrix (n, vector (n)); //using bool type could cause the `Time Limit Error` vector< vector > matrix (n, vector (n)); // Dynamic Programming // 1) if i == j, then matrix[i][j] = true; // 2) if i != j, then matrix[i][j] = (s[i]==s[j] && matrix[i+1][j-1]) for (int i=n-1; i>=0; i--){ for (int j=i; j 3, then, check s[i]==s[j] && matrix[i+1][j-1] if ( i==j || (s[i]==s[j] && (j-i<2 || matrix[i+1][j-1]) ) ) { matrix[i][j] = true; if (longest.size() < j-i+1){ longest = s.substr(i, j-i+1); } } } } return longest; } // Optimized DP soltuion can be accepted by LeetCode. string longestPalindrome_dp_opt_way(string s) { int n = s.size(); if (n<=1) return s; //Construct a matrix, and consdier matrix[j][i] as s[i] -> s[j] is Palindrome or not. // ------^^^^^^ // NOTE: it's [j][i] not [i][j] //Using vector could cause the `Time Limit Error` //So, use the native array bool **matrix = (bool**)malloc(n*sizeof(bool*)); int start=0, len=0; // Dynamic Programming // 1) if i == j, then matrix[i][j] = true; // 2) if i != j, then matrix[i][j] = (s[i]==s[j] && matrix[i-1][j+1]) for (int i=0; i 3, then, check s[i]==s[j] && matrix[i-1][j+1] if ( i==j || (s[j]==s[i] && (i-j<2 || matrix[i-1][j+1]) ) ) { matrix[i][j] = true; if (len < i-j+1){ start = j; len = i-j+1; } } } } for (int i=0; i 1){ s = argv[1]; } cout << s << " : " << longestPalindrome(s) << endl; s = "321012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210012321001232100123210123210012321001232100123210123"; cout << s << " : " << longestPalindrome(s) << endl; //"illi" s = "iptmykvjanwiihepqhzupneckpzomgvzmyoybzfynybpfybngttozprjbupciuinpzryritfmyxyppxigitnemanreexcpwscvcwddnfjswgprabdggbgcillisyoskdodzlpbltefiz"; cout << s << " : " << longestPalindrome(s) << endl; return 0; }
6. C 语言
#include#include #include static inline int min(int a, int b) { return a < b ? a : b; } static int manacher(char *s, char output[]) { int i, j; char s2[3000] = { '\0' }; s2[0] = '$'; for (i = 0; s[i] != '\0'; i++) { s2[(i<<1)+1] = '#'; s2[(i<<1)+2] = s[i]; } s2[(i<<1)+1] = '#'; int len = (i<<1)+2; s2[len] = '\0'; int p[3000] = { 0 }; // 以s2中某一点为中心的回文半径 int id = 0; // 回文的中心点 int limit = 0; // 最长回文的右边界点 int maxLen = 0; // 最大回文长度 int maxId = 0; // 最长回文的中心点 for (i = 1; i < len; i++) { if (i < limit) { p[i] = min(p[2*id-i], limit-i); } else { p[i] = 1; } while (s2[i+p[i]] == s2[i-p[i]]) { p[i]++; } if (i+p[i] > limit) { limit = i+p[i]; id = i; } if (maxLen < p[i]-1) { maxLen = p[i]-1; maxId = i; } } for (j = 0, i = maxId - maxLen; i <= maxId+maxLen; i++) { if (s2[i] != '#') { output[j++] = s2[i]; } } return maxLen; } static char *longestPalindrom(char *s) { int i; if (s == NULL) { return NULL; } int len = strlen(s); if (len <= 1) { return s; } char *palindrome = malloc(2000); memset(palindrome, 0, sizeof(palindrome)); int size = manacher(s, palindrome); palindrome[size] = '\0'; return palindrome; } int main(int argc, char **argv) { if (argc != 2) { fprintf(stderr, "Usage: ./test string "); exit(-1); } printf("%s ", longestPalindrom(argv[1])); return 0; }
看完上述内容,你们对数据结构中子串该怎么计算有进一步的了解吗?如果还想了解更多知识或者相关内容,请关注创新互联行业资讯频道,感谢大家的支持。