多种思路深度剖析经典面试题---最长回文子串

/* 验证子串 s[left...right]是否为回文子串 */
boolean isPalindrome(char[] charArray, int left, int right) {
    while (left < right) {
        if (charArray[left] != charArray[right]) {
            return false;
        }
        left++;
        right--;
    }

    return true;
} 

String longestPalindrome(String s) {
    int len = s.length();
    /* 长度少于 2 的字符串的最长回文子串是其自身 */
    if (len < 2) {
        return s;
    }

    int maxLen = 1;   // 记录最长回文子串的长度
    int start = 0;    // 记录最长回文子串的起始位置
    char[] charArray = s.toCharArray();
    for (int i = 0; i < len - 1; i++) {
        for (int j = i + 1; j < len; j++) {
            /* 回文子串 s[i...j] 的长度超过当前最长回文子串长度 */
            if (j - i + 1 > maxLen && isPalindrome(charArray, i, j)) {
                /* 更新最长回文子串的长度 */
                start = i;
                maxLen = j - i + 1;
            }
        }
    }

    return s.substring(start, start + maxLen);
}

String longestPalindrome(String s) {
    int len = s.length();
    if (len < 2) {
        return s;
    }

    int start = 0;
    int maxLen = 1;

    /* dp[i][j]：s[i...j] 是否是回文串 */
    boolean[][] dp = new boolean[len][len];
    for (int i = 0; i < len; i++) {
        dp[i][i] = true;
    }

    char[] charArray = s.toCharArray();
    for (int j = 1; j < len; j++) {
        for (int i = 0; i < j; i++) {
            if (charArray[i] != charArray[j]) {
                dp[i][j] = false;
            } else {
                if (j - i < 3) {
                    dp[i][j] = true;
                } else {
                    dp[i][j] = dp[i + 1][j - 1];
                }
            }

            /* s[i...j] 是回文串，记录当前最长回文串长度和起始位置 */
            if (dp[i][j] && j - i + 1 > maxLen) {
                maxLen = j - i + 1;
                start = i;
            }
        }
    }

    return s.substring(start, start + maxLen);
} 

/* s[left] 和 s[right] 想两断扩散， 求以 s[left] 和 s[right] 为中心的最长回文串*/
string longestPalindromeHelper(string s, int left, int right) { 
    while (left >= 0 && right < s.length() && s[left] == s[right]) {
        left--;
        right++;
    }
    
    return s.substr(left + 1, right - left - 1);
}

string longestPalindrome(string s) {
    int len = s.length();
    if (len < 2) {
        return s;
    }

    string res;
    for (int i = 0; i < len; i++) {
        /* 以s[i]作奇数回文子串的的回文中心向两边扩散，得到的最长回文子串*/
        string s1 = longestPalindromeHelper(s, i, i);
        /* 以s[i]、s[i + 1] 分别作偶数回文子串的的回文中心向两边扩散，得到的最长回文子串*/
        string s2 = longestPalindromeHelper(s, i, i + 1);
        res = res.size() > s1.size() ? res : s1;
        res = res.size() > s2.size() ? res : s2;
    }

    return res;
}