java beat 99.8%


  • 1
    L

    //思路:dp[i]代表从位置i开始的字串的最长字串长度
    //此题是通过不断“增加”字符串长度来更新以前的dp[i]
    //比如当前判断到s[0:i],增加i+1后,则dp[0:i]都要更新
    //比如当前已经判断完子字符串s(a,a,b,a),则dp[0~3]={3,2,1,1}
    //如果再增加一个元素a,即此时字符串为s(a,a,b,a,a),则dp[0~3]就得更新了:
    //更新应该从(i~0),因为起始位置靠前的依赖起始位置靠后的,所以应该先更新起始位置靠后的
    //此例先更新dp[3],因为s(3)==s(4),所以dp[3]=2;
    //因为dp[2]包含了dp[3],所以应该考虑dp[2]=2
    //要注意在更新的时候,如果s[i]==s[j],则s[i]=l+2;其中l是(i,j]中最长的对称字串
    //beat 99.8%
    0_1491827664380_360截图20170410203319404.png link text


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.