回文子串

刘勋 · 刘勋 · commit 7085a7187b87 · 2020-05-21T15:42:17.000+08:00
diff --git a/src/main/java/com/algorithm/study/demo/algorithm/leetcode/Solution10.java b/src/main/java/com/algorithm/study/demo/algorithm/leetcode/Solution10.java
@@ -0,0 +1,58 @@
+package com.algorithm.study.demo.algorithm.leetcode;
+
+import com.alibaba.fastjson.JSON;
+
+import java.util.ArrayList;
+import java.util.List;
+
+/**
+ * @author xun2.liu
+ * @title: Solution10
+ * @projectName algorithm-study
+ * @description: 给定一个字符串，你的任务是计算这个字符串中有多少个回文子串。
+ *
+ * 具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被计为是不同的子串。
+ *
+ * 示例 1:
+ *
+ * 输入: "abc"
+ * 输出: 3
+ * 解释: 三个回文子串: "a", "b", "c".
+ * 示例 2:
+ *
+ * 输入: "aaa"
+ * 输出: 6
+ * 说明: 6个回文子串: "a", "a", "a", "aa", "aa", "aaa".
+ *
+ * 来源：力扣（LeetCode）
+ * 链接：https://leetcode-cn.com/problems/palindromic-substrings
+ * @date 2020/5/21 15:34
+ */
+public class Solution10 {
+    //通过中心扩散法查找回文字符串
+    public static void huiwen(String s,int l,int r,List<String> filter){
+        while(l>=0 && r<s.length() && s.charAt(l)==s.charAt(r)){
+            l--;r++;
+            filter.add(s.substring(l+1,r));
+        }
+    }
+
+    public static int countSubstrings(String s) {
+        if(null==s || s.length()==0){
+            return 0;
+        }
+        if(s.length()==1){
+            return 1;
+        }
+        List<String> filter=new ArrayList<String>();
+        for(int i=0;i<s.length();i++){
+            huiwen(s,i,i,filter);
+            huiwen(s,i,i+1,filter);
+        }
+        return filter.size();
+    }
+
+    public static void main(String[] args) {
+        System.out.println(countSubstrings("aaa"));
+    }
+}
diff --git a/src/main/java/com/algorithm/study/demo/algorithm/leetcode/Solution9.java b/src/main/java/com/algorithm/study/demo/algorithm/leetcode/Solution9.java
@@ -0,0 +1,59 @@
+package com.algorithm.study.demo.algorithm.leetcode;
+
+import org.apache.commons.lang3.StringUtils;
+
+/**
+ * @author xun2.liu
+ * @title: Solution9
+ * @projectName algorithm-study
+ * @description: 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
+ *
+ * 示例 1：
+ *
+ * 输入: "babad"
+ * 输出: "bab"
+ * 注意: "aba" 也是一个有效答案。
+ * 示例 2：
+ *
+ * 输入: "cbbd"
+ * 输出: "bb"
+ *
+ * 来源：力扣（LeetCode）
+ * 链接：https://leetcode-cn.com/problems/longest-palindromic-substring
+ * @date 2020/5/21 13:46
+ */
+public class Solution9   {
+    /**
+     * 通过中心点向两边扩散。
+     * @param s
+     * @param r
+     * @param l
+     * @return
+     */
+    public static String palindrome(String s,int l,int r){
+        while (l>=0 && r<s.length() && s.charAt(r)==s.charAt(l)){
+            l--;r++;
+        }
+        //截取l-r中间的字符
+        return s.substring(l+1,r);
+    }
+    public static String longestPalindrome(String s) {
+        if (StringUtils.isBlank(s) || s.length()==1){
+            return s;
+        }
+        String res="";
+        for (int i=0;i<s.length()-1;i++){
+            //判断aba汇文字符串
+            String p1 = palindrome(s, i, i);
+            //判断aa回文字符串
+            String p2 = palindrome(s, i, i+1);
+            System.out.println(p1);
+            res=res.length()>=p1.length()?res:p1;
+            res=res.length()>=p2.length()?res:p2;
+        }
+        return res;
+    }
+    public static void main(String[] args) {
+        System.out.println(longestPalindrome("abc"));
+    }
+}
