经典算法(一)之回文

xiaoxiao2021-02-27  482

回文,把相同的词汇或句子 ,在下文中调换位置或颠倒过来,产生首尾回环的情趣,叫做回文。 例如: ABCDDCBA就是一个回文,ABA也是。 往往求一段字符串中的最长回文,是最常见的题型。

package com.zl.spider.test; import java.util.Scanner; /** * 求字符串最长回文算法 * * @author zl * @time 2017.05.03 */ public class PalindromicSubstring { private static String answer; private static int lo, maxlen; public static void main(String[] args) { System.out.println("请输入字符串:"); Scanner sc = new Scanner(System.in); String str = sc.next(); answer = longestPalindromicSubstring(str); System.out.println("最长回文为:" + answer); } private static String longestPalindromicSubstring(String str) { int len = str.length(); if (len < 2) { return str; } for (int i = 0; i < len - 1; i++) { extendPalindrome(str, i, i); extendPalindrome(str, i, i + 1); } return str.substring(lo, lo + maxlen); } private static void extendPalindrome(String str, int j, int k) { while (j >= 0 && k < str.length() && str.charAt(j) == str.charAt(k)) { j--; k++; } if (maxlen < k - j - 1) { lo = j + 1; maxlen = k - j - 1; } } }

运行结果:


每天一个算法,提高自己


转载请注明原文地址: https://www.6miu.com/read-135.html

最新回复(0)