问题描述

java求教，算法竞赛入门经典 3.4 最长回文子串

java新手求教，关键是怎么保存s[i]在buf中的位置，谢谢

解决方案

string longestPalindromeDP(string s) {
int n = s.length();

int longestBegin = 0;

int maxLen = 1;

bool table[1000][1000] = {false};

for (int i = 0; i < n; i++) {

table[i][i] = true;   //前期的初始化

}

for (int i = 0; i < n-1; i++) {

if (s[i] == s[i+1]) {

  table[i][i+1] = true; //前期的初始化

  longestBegin = i;

  maxLen = 2;

}

}

for (int len = 3; len <= n; len++) {

for (int i = 0; i < n-len+1; i++) {

  int j = i+len-1;

  if (s[i] == s[j] && table[i+1][j-1]) {

    table[i][j] = true;

    longestBegin = i;

    maxLen = len;

  }

}

}

return s.substr(longestBegin, maxLen);

}
这个是时间复杂度为O(n2)的

解决方案二：

好像，好复杂的样子啊！