本文共 2516 字,大约阅读时间需要 8 分钟。
[DP题解] 最长回文字符串问题
【问题】输入一个字符串,求出其中最长的回文子串。 子串的含义是:在原串中连续出现的字符串片段。回文的含义是:子串从左向右看和从右向左看是相同的,例如:abba,yyxyy。 在判断时忽略所有标点符号和空格,且忽略大小写,但是输出应保持原样。输入字符串的长度不超过5000,且占据单独一行。 应该输出最长的回文串。如果有多个,输出起始位置最靠左的一个。
[算法设计]
/* * 动态规划算法 dp(i, j) represents whether s(i ... j) can form a palindromic * substring, dp(i, j) is true when s(i) equals to s(j) and s(i+1 ... j-1) is a * palindromic substring. When we found a palindrome, check if it’s the longest * one. */ public static String longestPalindrome(String s) { // n表示字符串的长度 int n = s.length(); String res = null; // 定义一个dp数组 boolean[][] dp = new boolean[n][n]; // 外层循环控制从最后一个字符向第一个字符渐进 for (int i = n - 1; i >= 0; i--) { // 内层循环控制 for (int j = i; j < n; j++) { // dp数组元素 dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]); if (dp[i][j] && (res == null || j - i + 1 > res.length())) { res = s.substring(i, j + 1); } } } return res; }
输入样例:
fafadabcbafdfdfas
fafdafayyxyyffdadaa afdfdafabcabcbafdfdafxxxxxxxxyyyyxyyxxyyx
完整的代码:
package com.bean.algorithmexec;import java.io.FileInputStream;import java.io.FileNotFoundException;import java.util.Scanner;public class LongestPalindromeString2 { /* * 输入一个字符串,求出其中最长的回文子串。 子串的含义是:在原串中连续出现的字符串片段。 * 回文的含义是:子串从左向右看和从右向左看是相同的,例如:abba,yyxyy。 在判断时忽略所有标点符号和空格,且忽略大小写,但是输出应保持原样。 * 输入字符串的长度不超过5000,且占据单独一行。 应该输出最长的回文串。如果有多个,输出起始位置最靠左的一个。 * */ /* * 动态规划算法 dp(i, j) represents whether s(i ... j) can form a palindromic * substring, dp(i, j) is true when s(i) equals to s(j) and s(i+1 ... j-1) is a * palindromic substring. When we found a palindrome, check if it’s the longest * one. */ public static String longestPalindrome(String s) { // n表示字符串的长度 int n = s.length(); String res = null; // 定义一个dp数组 boolean[][] dp = new boolean[n][n]; // 外层循环控制从最后一个字符向第一个字符渐进 for (int i = n - 1; i >= 0; i--) { // 内层循环控制 for (int j = i; j < n; j++) { // dp数组元素 dp[i][j] = s.charAt(i) == s.charAt(j) && (j - i < 3 || dp[i + 1][j - 1]); if (dp[i][j] && (res == null || j - i + 1 > res.length())) { res = s.substring(i, j + 1); } } } return res; } public static void main(String[] args) throws FileNotFoundException { // TODO Auto-generated method stub System.setIn(new FileInputStream("G:\\LongestPalindromeString.txt")); Scanner sc = new Scanner(System.in); while (sc.hasNextLine()) { // 读取输入的字符串 String strdemo = sc.nextLine(); String ANSWER = longestPalindrome(strdemo); System.out.println("#: " + ANSWER); } }}
输出结果:
#: afdfdfa
#: yyxyy #: xyyxxyyx
转载地址:http://ydtdi.baihongyu.com/