由构造回文字串的算法问题引发思考 | 指尖的舞客

由构造回文字串的算法问题引发思考 | 指尖的舞客

参考代码： /** * 最大公共子序列的应用 * @author hyw * */ public class ConstructPalidrome { private static String LCS(String s1, String s2){ if(s1 == null || s2 == null) return null; int len1 = s1.length(); int len2 = s2.length(); int[][] f = new int[len1+1][len2+1]; for(int i=len1-1; i>=0; i--) for(int j=len2-1; j>=0; j--){ if(s1.charAt(i) == s2.charAt(j)){ f[i][j] = f[i+1][j+1] + 1; }else{ f[i][j] = Math.max(f[i+1][j], f[i][j+1]); } } int i=0, j=0; StringBuilder sb = new StringBuilder(); while(i f[i][j+1]){ i++; }else{ j++; } } return sb.toString(); } public static boolean isPalin(String str){ if(str == null || str.length() < 3) return true; String strReverse = new StringBuilder(str).reverse().toString(); String sub = LCS(str, strReverse); return Math.abs(str.length() - sub.length()) <= 1; } public static void main(String[] args){ String str = "testset"; if(isPalin(str)){ System.out.

Read full article from 由构造回文字串的算法问题引发思考 | 指尖的舞客