[回文系列] 回文数、最长回文子串、最长回文子序列

雨点打透心脏的1/2处 2024-04-18 16:59 102阅读 0赞

# 1、验证回文数 #

LintCode：[https://www.lintcode.com/problem/palindrome-number/description][https_www.lintcode.com_problem_palindrome-number_description]

**题目描述**：判断一个正整数是不是回文数。  
回文数的定义是，将这个数反转之后，得到的数仍然是同一个数。

**样例**  
例1：

输入：11  
输出：true

例2：

输入：1232  
输出：false  
解释：  
1232!=2321

**注意事项**  
给的数一定保证是32位正整数，但是反转之后的数就未必了。因此，可以将int型数字转化为字符串来处理。

**代码**：

public class Solution {
        /**
         * @param num: a positive number
         * @return: true if it's a palindrome or false
         */
        public boolean isPalindrome(int num) {
            // write your code here
            StringBuilder sb = new StringBuilder();
            while(num != 0){
                sb.append(""+num % 10);
                num = num / 10;
            }
            int i = 0, j = sb.length() - 1;
            while(i < j){
                if(sb.charAt(i) != sb.charAt(j)){
                    return false;
                }
                i ++;
                j --;
            }
            return true;
        }
    }

# 2、最长回文子串 #

**LintCode**：[https://www.lintcode.com/problem/longest-palindromic-substring/description][https_www.lintcode.com_problem_longest-palindromic-substring_description]

**题目描述**：给出一个字符串（假设长度最长为1000），求出它的最长回文子串，你可以假定只有一个满足条件的最长回文串。

**样例**  
样例 1:

输入:“abcdzdcab”  
输出:“cdzdc”  
样例 2:

输入:“aba”  
输出:“aba”

代码：

//方法一：使用共享变量
    
    public class LongestPalindrmicSubString {
        /**
         * @param s: input string
         * @return: the longest palindromic substring
         */
        String maxSubString = "";
    
        public String longestPalindrome(String s) {
            // write your code here
            if(s == null || s.length() == 0)
                return null;
            for(int i = 0; i < s.length() - 1; i ++){
                getMaxLen(s, i, i+1);
            }
    
            for(int i = 0; i <= s.length() - 1; i ++){
                getMaxLen(s, i, i);
            }
            return maxSubString;
        }
    
        /**
         * 计算start和end为中点向两边出发时，可寻找的最长回文子串
         *
         * start == end时，最终的回文子串就是奇数长度
         *
         * start + 1 == end时，最终的回文子串就是偶数长度
         */
        private void getMaxLen(String str, int start, int end){
            if(start > end || str == null || str.length() == 0)
                return;
            int i = start, j = end;
            int cnt = 0;
            while(i >= 0 && j < str.length() && str.charAt(i) == str.charAt(j)){
                i --; j ++;
    
                cnt += (i == j) ? 1 : 2;  //回文串长度的统计，注意长度+1 和长度 +2的区别
            }
            if(cnt > maxSubString.length())
                maxSubString = str.substring(i + 1, j);
            return;
        }
    
        @Test
        public void test(){
            //test case
            String a = "ccc";
            String b = "bcbaaaaa";
            System.out.println(longestPalindrome(a));
        }

(1)针对回文子串的中点有两种情况，一种是奇数长度回文子串，中间的起点`i = j`；一种是偶数长度的回文子串，中间的起点`i + 1 = j`。

(2)一定要注意回文子串长度在统计时的问题，如果`i = j`，回文子串的长度`+1`，如果`i != j`，对应的回文子串的长度应该时 `+2`。

(3)注意`String`的`subString(int start, int end)`方法，返回的字符串是`[start, end)`。也就是`charAt(end)` 是不包含返回的子串当中。

//方法二：子函数传递回文子串起点和终点
    /**
     * @author wanglong
     * @brief
     * @date 2019-08-18 12:45
     */
    import org.junit.Test;
    public class LongestPalindormeSub {
    
        //基于中心点枚举的算法，时间复杂度 O(n^2)
        /**
         * @param s: input string
         * @return: the longest palindromic substring
         */
        public String longestPalindrome(String s) {
            if(s == null || s.length() == 0)
                return null;
            int maxLen = 0;
            int startPoint = 0, endPoint = 0;
            for(int i = 0; i < s.length(); i ++){
                int[] point = new int[2];
                int oddRes = getLongestStr(s, i, i, point);
                if(oddRes > maxLen){
                    maxLen = oddRes;
                    startPoint = point[0];
                    endPoint = point[1];
                }
                int evenRes = getLongestStr(s,i,i + 1, point);
                if(evenRes > maxLen){
                    maxLen = evenRes;
                    startPoint = point[0];
                    endPoint = point[1];
                }
            }
            return s.substring(startPoint,endPoint + 1);
        }
    
        /**
         * 从right向右，从left向左，寻找回文串
         *  <---left right-->
        */
        private int getLongestStr( String str, int left, int right, int[] endPoint){
            int len = 0;
            while(right <= str.length() -  1 && right >=0
                    && left <= str.length() - 1 && left >= 0){
                if(str.charAt(right) == str.charAt(left)) {
                    len += (right==left) ? 1 : 2;
                    endPoint[0] = left;
                    endPoint[1] = right;
                }else
                    break;
                left --;
                right ++;
            }
    
            return len;
        }
    
        @Test
        public void test(){
            String s1 ="abcdzdcab";
            System.out.println(longestPalindrome(s1)); //cdzdc
            String s2 ="abcdz121zdcab";
            System.out.println(longestPalindrome(s2)); //cdz121zdc
            String s3 ="aba";
            System.out.println(longestPalindrome(s3)); //aba
            String s4 ="a";
            System.out.println(longestPalindrome(s4)); //aba
            String s5 ="bb";
            System.out.println(longestPalindrome(s5)); //bb
            System.out.println(longestPalindrome(badcase1()));
        }
    
    	//badCase
        //Sting较大时，作为函数返回时在代码提交时会内存不足
        //修改getLongestStr方法，不再直接返回String字符串，而是返回长度便于比较，同时将起点和终点通过形参返回。
        //上述的改动即可解决内存不足的问题
        String badcase1(){
            return "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
        }
    }
    
    //九章提供的o(n)的解法： https://www.jiuzhang.com/solution/longest-palindromic-substring/
    //参考博客：https://www.felix021.com/blog/read.php?2040

> 不论是回文数、还是回文子串，都是基于回文的判断，后者也就是确定中点的一种判断。下面的回文子序列则与之前的题目不一样，因为回文串不再是连续的，需要利用动态规划的思想。

# 3、最长回文子序列 #

**LintCode**：[https://www.lintcode.com/problem/longest-palindromic-subsequence/description][https_www.lintcode.com_problem_longest-palindromic-subsequence_description]

**题目描述**：最长的回文序列

给一字符串 s, 找出在 s 中的最长回文子序列的长度. 你可以假设 s 的最大长度为 1000.

**样例**  
样例1

输入： “bbbab”  
输出： 4  
解释：  
一个可能的最长回文序列为 “bbbb”  
样例2

输入： “bbbbb”  
输出： 5

**分析**：针对头尾指针分别为i和j的字符串`c[abac]c`，设`[]`外的字符分别为首字符和尾字符。头指针`i`指向首字符`c`，尾指针`j`也是指向尾字符`c`。可以推测该字符串中最长回味子序列的长度与`[abac]`中回文子序列的长度有关。

如果指针`i`和指针`j`指向的字符相等，那么即在`[abac]`中回文子序列的长度上`+2`。相对比较简单。

如果指针`i`和指针`j`指向的字符不相等，例如`c[abac]d`或者`c[baba]b`，那么最长回文子序列可能会出现两种情况。该最长回文子序列的长度为`i + 1 ~ j`或者 `i ~ j - 1`区间上的最长回文子序列的长度。`c[abac]d`的最长回文子序列即为 `i ~ j - 1`上的最长回文子序列`c[abac]`，而`c[baba]b`的最长回文子序列为`[baba]b`。

根据以上的分析，不难得出一下的动态规划的转移方程。

设f[i][j]表示以i为起点，j为终点的字符串中最长回文子序列的长度
    if  (str.charAt(i) == str.charAt(j))
    	f[i][j] = f[i + 1][j - 1] + 2
    else
    	f[i][j] = Math.max(f[i + 1][j], f[i][j - 1])

写出该题的转移方程是相对简单的。初始化和计算方向的确定才是本题的难点。我们发现状态转移方程中，长度较长的字符串的结果 依赖 长度较短的字符串的结果，那么也就是在计算较长长度之前要先完成短长度的计算。

举例来说，要计算`f[1][4],` 必须要首先知道`f[2][3]`、`f[1][3]`、`f[2][4]`. 其中`f[2][3]`我们发现使用转移方程计算时会使用`f[0][0]+f[3][2]`、`f[2][2]`、`f[3][3]`。其中`f[3][2]=0`；

**代码**：

import org.junit.Test;
    
    /**
     * @author wanglong
     * @brief
     * @date 2019-09-09 23:06
     */
    
    
    public class LongestPalindromicSubsequence {
        /**
         * @param s: the maximum length of s is 1000
         * @return: the longest palindromic subsequence's length
         */
        public int longestPalindromeSubseq(String s) {
            // write your code here
            if(s == null || s.length() == 0)
                return 0;
            int[][] f = new int[s.length()][s.length()]; // [i,j]字符串中对应的最长回文子序列的长度
            for(int i = 0; i <= s.length() - 1; i ++){
                f[i][i] = 1;
            }
            for(int len = 2; len <= s.length(); len ++){  //外层循环为长度，必须保证所有短长度计算完后，才能计算长长度。
                for(int i = 0; i < s.length() - 1 && i + len - 1 < s.length(); i ++){  //内层循环注意j的范围，防止s.charAt(j)越界
                    int j = i + len - 1;
                    if(s.charAt(i) == s.charAt(j))
                        f[i][j] = f[i+1][j-1]+2;
                    else
                        f[i][j] = Math.max(f[i+1][j],f[i][j-1]);
                }
            }
            return f[0][s.length() - 1];
        }
    
        @Test
        public void test(){
            //test case
            String a = "bbbacab"; //5
            String b = "asdasdajjdkajwiejladjkahsdjhawiueauwhdjashdjancnkjsahduiawudhajsnhsjahjdhawuahdjshjnzanjcnhjdashuawhdjaksndjkahduwhwauhdai"; //69
            String c ="a";
            System.out.println(longestPalindromeSubseq(b));
        }
    }

以上代码的状态转移方程`f[i][j]`是按照字符串的长度`len`由小到大的顺序进行计算的，首先计算所有长度为`3`的字符串，然后计算计算长度为`4`的字符串，依次直到长度为`str.length()`。计算顺序的示意图如下所示，保证在计算较长长度时，其中的较短长度的已经计算完成：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvb25na2luZ3doYXQ_size_16_color_FFFFFF_t_70]  
当然还有另一种更加简单的计算方向，如下图所示。外层循环从尾部开始直到头部结束。内层循环控制起点到终点的长度，完成该起点处所有长度的计算。由起点的范围是在不断扩展，也就是最长的字符串在不断的变长。这样的计算方向下，也可以保证在计算较长长度时，其内的较短长度的已经计算完成。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvb25na2luZ3doYXQ_size_16_color_FFFFFF_t_70 1]  
该种计算方向下的代码如下所示：

public class Solution {
       public int longestPalindromeSubseq(String s) {
            if(s == null || s.length() == 0)
                return 0;
            int[][] f = new int[s.length()][s.length()]; //f[i][j] [i,j]区间对应字符串中最大回文子序列的长度
            for(int i = s.length() - 1; i >= 0; i --){
                f[i][i] = 1;
                for(int j = i + 1; j < s.length(); j ++){
                    if(s.charAt(i) == s.charAt(j))
                        f[i][j] = f[i + 1][j - 1]  + 2; 
                    else
                        f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
                }
            }
            return f[0][s.length() - 1];
        }
    }

[https_www.lintcode.com_problem_palindrome-number_description]: https://www.lintcode.com/problem/palindrome-number/description
[https_www.lintcode.com_problem_longest-palindromic-substring_description]: https://www.lintcode.com/problem/longest-palindromic-substring/description
[https_www.lintcode.com_problem_longest-palindromic-subsequence_description]: https://www.lintcode.com/problem/longest-palindromic-subsequence/description
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvb25na2luZ3doYXQ_size_16_color_FFFFFF_t_70]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/bc52453d65444417910f0ff137c8cd4a.jpeg
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xvb25na2luZ3doYXQ_size_16_color_FFFFFF_t_70 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/9b8313f28375433d9dc3fa0bb739ccea.jpeg