个人随笔
目录
leetcode(三)、最长回文子串
2021-06-17 18:17:03

给你一个字符串 s，找到 s 中最长的回文子串。

  • 示例 1：输入：s = “babad” 输出：”bab” 解释：”aba” 同样是符合题意的答案。
  • 示例 2：输入：s = “cbbd” 输出：”bb”
  • 示例 3：输入：s = “a” 输出：”a”
  • 示例 4：输入：s = “ac” 输出：”a”
  • 提示：1 <= s.length <= 1000 s 仅由数字和英文字母（大写和/或小写）组成
  1. public class Test5 {
  2.     /**
  3.      * 先尝试穷举法1：判断每个字符开始和相同字符结束的串是否构成回文，若构成则继续判断下一个相同的字符
  4.      * 执行用时：450 ms, 在所有 Java 提交中击败了10.68%的用户内存消耗：39.1 MB, 在所有 Java 提交中击败了53.96%的用户
  5.      * @param s
  6.      * @return
  7.      */
  8.     public String longestPalindrome(String s) {
  9.         //1、设置最长子串的长度
  10.         int maxLen = 1;
  11.         String result = s.charAt(0)+"";
  12.         System.out.println(s.length());
  13.         //2、循环处理每个字符串
  14.         for(int i=0;i<s.length();i++) {
  15.             //3、获取当前字符开头的子串
  16.             char now = s.charAt(i);
  17.             //4、判断后续与当前字符相同的字符，看啊可能是否能够构成回文,这里直接从后面开始判断
  18.             for(int j=i+1;j<s.length();j++) {
  19.                 char next = s.charAt(j);
  20.                 if(now==next) {
  21.                     //检查这两个字符之间是否构成回文，也就是第一位等于最后一位
  22.                     int num = j-i+1;//获取两个相同字符之间的字符数
  23.                     if(num<=maxLen) {
  24.                         //这里就没有必要判断这个了,不加这个回运行超时
  25.                         continue;
  26.                     }
  27.                     int len =num/2;
  28.                     boolean flag=true;
  29.                     for(int k=0;k<len;k++) {
  30.                         //检查是否是回文
  31.                         if(s.charAt(i+k)!=s.charAt(j-k)) {
  32.                             //不是回文
  33.                             flag=false;
  34.                             break;
  35.                         }
  36.                     }
  37.                     if(flag) {
  38.                         //这里表明从i到j是回文，长度为len
  39.                         System.out.println("从下标"+i+"到"+j+"构成回文："+s.substring(i, j+1)+"长度为"+num);
  40.                         if(num>maxLen) {
  41.                             maxLen=num;
  42.                             result=s.substring(i, j+1);
  43.                         }
  44.                     }
  47.                 }
  48.             }
  49.         }
  51.         return result;
  52.     }
  54.     /**
  55.      * 先尝试穷举法2：穷举法1会导致同一个字符多次判断，比如abababa那边后面三个a都要判断，但是加入从后面往前判断就只需要判断最后一个a
  56.      * 这种方式比第一种效果好一点
  57.      * 执行用时：398 ms, 在所有 Java 提交中击败了13.99%的用户内存消耗：38.7 MB, 在所有 Java 提交中击败了65.25%的用户
  58.      * @param s
  59.      * @return
  60.      */
  61.     public String longestPalindrome2(String s) {
  62.         //1、设置最长子串的长度
  63.         int maxLen = 1;
  64.         int start_i=0;//开始下标
  65.         int end_i=0;//结束下标
  66.         //2、循环处理每个字符串
  67.         for(int i=0;i<s.length();i++) {
  68.             //3、获取当前字符开头的子串
  69.             char now = s.charAt(i);
  70.             //4、判断后续与当前字符相同的字符，看啊可能是否能够构成回文,这里直接从后面开始判断
  71.             for(int j=s.length()-1;j>i;j--) {
  72.                 char next = s.charAt(j);
  73.                 if(now==next) {
  74.                     //检查这两个字符之间是否构成回文，也就是第一位等于最后一位
  75.                     int num = j-i+1;//获取两个相同字符之间的字符数
  76.                     if(num<=maxLen) {
  77.                         //这里就没有必要判断这个了,不加这个回运行超时
  78.                         continue;
  79.                     }
  80.                     int len =num/2;
  81.                     boolean flag=true;
  82.                     for(int k=0;k<len;k++) {
  83.                         //检查是否是回文
  84.                         if(s.charAt(i+k)!=s.charAt(j-k)) {
  85.                             //不是回文
  86.                             flag=false;
  87.                             break;
  88.                         }
  89.                     }
  90.                     if(flag) {
  91.                         //这里表明从i到j是回文，长度为len
  92.                         //System.out.println("从下标"+i+"到"+j+"构成回文："+s.substring(i, j+1)+"长度为"+num);
  93.                         if(num>maxLen) {
  94.                             maxLen=num;
  95.                             start_i=i;
  96.                             end_i=j;
  97.                             //result=s.substring(i, j+1);
  98.                         }
  99.                         //这里如果有回文，直接判断下一个字符
  100.                         continue;
  101.                     }
  102.                 }
  103.             }
  104.         }
  105.         String result = s.substring(start_i, end_i+1);
  106.         System.out.println("最大回文长度为："+((end_i-start_i)+1)+"回文串为："+result);
  107.         return result;
  108.     }
  111.     /**
  112.      * 一维动态规划法:我他喵，果然比我的好很多
  113.      * 执行用时：17 ms, 在所有 Java 提交中击败了91.19%的用户内存消耗：38.6 MB, 在所有 Java 提交中击败了72.87%的用户
  114.      * @param s
  115.      * @return
  116.      */
  117.     public String longestPalindrome3(String s) {
  118.         int n = s.length();
  119.         // dp[j] 表示以位置 j 结尾的最长回文子串的起始位置
  120.         // 其长度就是 j - dp[j] + 1
  121.         int[] dp = new int[n];
  122.         dp[0] = 0;
  124.         // 记录最大回文子串的长度
  125.         // 0 - 0 + 1
  126.         int max_length = 1;
  127.         int start_i=0;//开始下标
  128.         int end_i=0;//结束下标
  129.         for (int j = 1; j < n; j++) {
  130.             if (dp[j - 1] > 0 && s.charAt(j) == s.charAt(dp[j - 1] - 1)) {
  131.                 // 当前位置的字符和上一次回文串的左邻字符相同
  132.                 // 回文串得到扩展
  133.                 dp[j] = dp[j - 1] - 1;
  134.             } else {
  135.                 // 从左向右找
  136.                 int left = dp[j - 1];
  137.                 int right = j;
  138.                 int start = left;  // 最近一次的回文查找起始位置
  140.                 while (left < right) {
  141.                     if (s.charAt(left) != s.charAt(right)) {
  142.                         // 遭遇失配字符，重置 right
  143.                         right = j;
  144.                         start = left + 1;
  145.                     } else {
  146.                         // 否则，两边继续收拢
  147.                         right--;
  148.                     }
  149.                     left++;
  150.                 }
  152.                 dp[j] = start;
  153.             }
  155.             // 更新最大值
  156.             int length = j - dp[j] + 1;
  157.             if (length > max_length) {
  158.                 max_length = length;
  159.                 end_i=j;
  160.                 start_i=dp[j];
  161.             } 
  162.         }
  163.         String result = s.substring(start_i, end_i+1);
  164.         System.out.println("最大回文长度为："+((end_i-start_i)+1)+"回文串为："+result);
  165.         return result;
  166.     }
  168.     /**
  169.      * 二维动态规划法:还是一维动态规划厉害
  170.      * 执行用时：311 ms, 在所有 Java 提交中击败了27.99%的用户内存消耗：42.4 MB, 在所有 Java 提交中击败了37.71%的用户
  171.      * @param s
  172.      * @return
  173.      * 
  174.      */
  175.     public String longestPalindrome4(String s) {
  176.         int n = s.length();
  177.         // dp[j] 表示以位置 j 结尾的最长回文子串的起始位置
  178.         // 其长度就是 j - dp[j] + 1
  179.         // 记录最大回文子串的长度
  180.         // 0 - 0 + 1
  181.         int max_length = 1;
  182.         int start_i=0;//开始下标
  183.         int end_i=0;//结束下标
  185.         // dp[i][j] 表示 s[i..j] 是否回文，j >= i
  186.         boolean[][] dp=new boolean[n][n];
  188.         // 初始化
  189.         for (int i = 0; i < n; i++)
  190.             for (int j = i; j < n; j++) dp[i][j] = false;
  192.         // 易知，单个字符 s[i..i] 构成回文
  193.         for (int i = 0; i < n; i++) dp[i][i] = true;
  195.         // 记录最大回文子串的长度，至少为 1
  196.         // 考虑递推
  197.         // 主要的递推关系是 dp[i][j] = dp[i+1][j-1]
  198.         // 所以倒序遍历 i ，才可以形成递推
  199.         for (int i = n - 1; i >= 0; i--) {
  200.             for (int j = i; j < n; j++) {
  201.                 if (s.charAt(i)== s.charAt(j)) {
  202.                     if (j - 1 >= i + 1) {  // 子串 s[i+1..j-1] 有效性
  203.                         if (dp[i + 1][j - 1]) dp[i][j] = true;
  204.                     } else {
  205.                         // 此时 j < i + 2 即 j <= i+1
  206.                         // 再之 s[i] == s[j]，必回文
  207.                         dp[i][j] = true;
  208.                     }
  209.                 }
  211.                 if (dp[i][j]) {
  212.                     // 更新最大长度
  213.                     int length = j - i + 1;
  214.                     if (length > max_length) {
  215.                         max_length = length;
  216.                         end_i=j;
  217.                         start_i=i;
  218.                     }
  220.                 }
  221.             }
  222.         }
  223.         String result = s.substring(start_i, end_i+1);
  224.         System.out.println("最大回文长度为："+((end_i-start_i)+1)+"回文串为："+result);
  225.         return result;
  226.     }
  227.     public static void main(String[] args) {
  228.         //String result = new Test5().longestPalindrome2("1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111");
  229.         //String result = new Test5().longestPalindrome3("abaasasdasd");
  230.         String result = new Test5().longestPalindrome4("acbcbcbc");
  231.         System.out.println("result:"+result);
  232.     }
  234. }

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-palindromic-substring
参考：动态规划部分：https://writings.sh/post/algorithm-longest-palindromic-substring

 240

啊！这个可能是世界上最丑的留言输入框功能~


当然，也是最丑的留言列表

有疑问发邮件到 : suibibk@qq.com 侵权立删
Copyright : 个人随笔   备案号 : 粤ICP备18099399号-2