个人随笔
目录
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. }
  45. }
  46. }
  47. }
  48. return result;
  49. }
  50. /**
  51. * 先尝试穷举法2:穷举法1会导致同一个字符多次判断,比如abababa那边后面三个a都要判断,但是加入从后面往前判断就只需要判断最后一个a
  52. * 这种方式比第一种效果好一点
  53. * 执行用时:398 ms, 在所有 Java 提交中击败了13.99%的用户内存消耗:38.7 MB, 在所有 Java 提交中击败了65.25%的用户
  54. * @param s
  55. * @return
  56. */
  57. public String longestPalindrome2(String s) {
  58. //1、设置最长子串的长度
  59. int maxLen = 1;
  60. int start_i=0;//开始下标
  61. int end_i=0;//结束下标
  62. //2、循环处理每个字符串
  63. for(int i=0;i<s.length();i++) {
  64. //3、获取当前字符开头的子串
  65. char now = s.charAt(i);
  66. //4、判断后续与当前字符相同的字符,看啊可能是否能够构成回文,这里直接从后面开始判断
  67. for(int j=s.length()-1;j>i;j--) {
  68. char next = s.charAt(j);
  69. if(now==next) {
  70. //检查这两个字符之间是否构成回文,也就是第一位等于最后一位
  71. int num = j-i+1;//获取两个相同字符之间的字符数
  72. if(num<=maxLen) {
  73. //这里就没有必要判断这个了,不加这个回运行超时
  74. continue;
  75. }
  76. int len =num/2;
  77. boolean flag=true;
  78. for(int k=0;k<len;k++) {
  79. //检查是否是回文
  80. if(s.charAt(i+k)!=s.charAt(j-k)) {
  81. //不是回文
  82. flag=false;
  83. break;
  84. }
  85. }
  86. if(flag) {
  87. //这里表明从i到j是回文,长度为len
  88. //System.out.println("从下标"+i+"到"+j+"构成回文:"+s.substring(i, j+1)+"长度为"+num);
  89. if(num>maxLen) {
  90. maxLen=num;
  91. start_i=i;
  92. end_i=j;
  93. //result=s.substring(i, j+1);
  94. }
  95. //这里如果有回文,直接判断下一个字符
  96. continue;
  97. }
  98. }
  99. }
  100. }
  101. String result = s.substring(start_i, end_i+1);
  102. System.out.println("最大回文长度为:"+((end_i-start_i)+1)+"回文串为:"+result);
  103. return result;
  104. }
  105. /**
  106. * 一维动态规划法:我他喵,果然比我的好很多
  107. * 执行用时:17 ms, 在所有 Java 提交中击败了91.19%的用户内存消耗:38.6 MB, 在所有 Java 提交中击败了72.87%的用户
  108. * @param s
  109. * @return
  110. */
  111. public String longestPalindrome3(String s) {
  112. int n = s.length();
  113. // dp[j] 表示以位置 j 结尾的最长回文子串的起始位置
  114. // 其长度就是 j - dp[j] + 1
  115. int[] dp = new int[n];
  116. dp[0] = 0;
  117. // 记录最大回文子串的长度
  118. // 0 - 0 + 1
  119. int max_length = 1;
  120. int start_i=0;//开始下标
  121. int end_i=0;//结束下标
  122. for (int j = 1; j < n; j++) {
  123. if (dp[j - 1] > 0 && s.charAt(j) == s.charAt(dp[j - 1] - 1)) {
  124. // 当前位置的字符和上一次回文串的左邻字符相同
  125. // 回文串得到扩展
  126. dp[j] = dp[j - 1] - 1;
  127. } else {
  128. // 从左向右找
  129. int left = dp[j - 1];
  130. int right = j;
  131. int start = left; // 最近一次的回文查找起始位置
  132. while (left < right) {
  133. if (s.charAt(left) != s.charAt(right)) {
  134. // 遭遇失配字符,重置 right
  135. right = j;
  136. start = left + 1;
  137. } else {
  138. // 否则,两边继续收拢
  139. right--;
  140. }
  141. left++;
  142. }
  143. dp[j] = start;
  144. }
  145. // 更新最大值
  146. int length = j - dp[j] + 1;
  147. if (length > max_length) {
  148. max_length = length;
  149. end_i=j;
  150. start_i=dp[j];
  151. }
  152. }
  153. String result = s.substring(start_i, end_i+1);
  154. System.out.println("最大回文长度为:"+((end_i-start_i)+1)+"回文串为:"+result);
  155. return result;
  156. }
  157. /**
  158. * 二维动态规划法:还是一维动态规划厉害
  159. * 执行用时:311 ms, 在所有 Java 提交中击败了27.99%的用户内存消耗:42.4 MB, 在所有 Java 提交中击败了37.71%的用户
  160. * @param s
  161. * @return
  162. *
  163. */
  164. public String longestPalindrome4(String s) {
  165. int n = s.length();
  166. // dp[j] 表示以位置 j 结尾的最长回文子串的起始位置
  167. // 其长度就是 j - dp[j] + 1
  168. // 记录最大回文子串的长度
  169. // 0 - 0 + 1
  170. int max_length = 1;
  171. int start_i=0;//开始下标
  172. int end_i=0;//结束下标
  173. // dp[i][j] 表示 s[i..j] 是否回文,j >= i
  174. boolean[][] dp=new boolean[n][n];
  175. // 初始化
  176. for (int i = 0; i < n; i++)
  177. for (int j = i; j < n; j++) dp[i][j] = false;
  178. // 易知,单个字符 s[i..i] 构成回文
  179. for (int i = 0; i < n; i++) dp[i][i] = true;
  180. // 记录最大回文子串的长度,至少为 1
  181. // 考虑递推
  182. // 主要的递推关系是 dp[i][j] = dp[i+1][j-1]
  183. // 所以倒序遍历 i ,才可以形成递推
  184. for (int i = n - 1; i >= 0; i--) {
  185. for (int j = i; j < n; j++) {
  186. if (s.charAt(i)== s.charAt(j)) {
  187. if (j - 1 >= i + 1) { // 子串 s[i+1..j-1] 有效性
  188. if (dp[i + 1][j - 1]) dp[i][j] = true;
  189. } else {
  190. // 此时 j < i + 2 即 j <= i+1
  191. // 再之 s[i] == s[j],必回文
  192. dp[i][j] = true;
  193. }
  194. }
  195. if (dp[i][j]) {
  196. // 更新最大长度
  197. int length = j - i + 1;
  198. if (length > max_length) {
  199. max_length = length;
  200. end_i=j;
  201. start_i=i;
  202. }
  203. }
  204. }
  205. }
  206. String result = s.substring(start_i, end_i+1);
  207. System.out.println("最大回文长度为:"+((end_i-start_i)+1)+"回文串为:"+result);
  208. return result;
  209. }
  210. public static void main(String[] args) {
  211. //String result = new Test5().longestPalindrome2("1111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111");
  212. //String result = new Test5().longestPalindrome3("abaasasdasd");
  213. String result = new Test5().longestPalindrome4("acbcbcbc");
  214. System.out.println("result:"+result);
  215. }
  216. }

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

 196

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


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

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