LeetCode算法：求出字元串的最大回文子串 及 長度【隻利用字元串反轉就可】

• 給你一個字元串 s，找到 s 中最長的回文子串。
• 輸入：s = “babad”
• 輸出：“bab”

• 解釋：“aba” 同樣是符合題意的答案。

  題目思路:

  判斷是不是回文串：隻需要反轉後判斷是不是相等

  然後求出所有的子串 并 判斷是不是回文，傳回最大的即可

/**
 * @author Captain
 * @date 2021/8/19 9:53
 * 給你一個字元串 s，找到 s 中最長的回文子串。
 * 輸入：s = "babad"
 * 輸出："bab"
 * 解釋："aba" 同樣是符合題意的答案。
 */
public class LongestPalindrome {

    public static String longestPalindrome(String string) {
        
        // 用來裝所有的回文子串
        ArrayList<String> list = new ArrayList<>();

        // 周遊字元串的所有子串
        for (int i = 0; i < string.length(); i++) {
            for (int j = 1; j <= string.length() - i; j++) {
                String sub = string.substring(i,i+j);
                // 如果子串長度大于一 && 是回文串
                if (sub.length()>1 && isPalindorm(sub)){
                    list.add(sub);
                }
            }
        }
        
        // 定義一個最大回文的長度
        int max = 0;

        for (int i = 0; i < list.size(); i++) {
            max = Math.max(max,list.get(i).length());
        }
        
        // 取出最大回文子串
        for (int i = 0; i < list.size(); i++) {
            if (list.get(i).length() == max){
                return list.get(i);
            }
        }
        
        return "";

    }

    // 判斷是不是回文串
    public static boolean isPalindorm(String s){
        StringBuilder sb = new StringBuilder(s);
        if (sb.reverse().toString().equals(s)){
            return true;
        }
        return false;
    }

    // 主函數測試
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String string = sc.nextLine();
        System.out.println(longestPalindrome(string));
    }
}