LeetCode||查找字符串中的最长回文字符串

系统管理员 2021-11-09 15:28 375阅读 0赞

### 回文字符串 ###

回文字符串就是正着读和反着读都一样的字符串，例如abcdcba

### 算法--动态规划 ###

用一个boolean类型的二维数组T\[i\]\[j\]来表示i到j之间的字符串是否回文

其中 i>=j 动态规划的初值就是 当i=j时，T\[i\]\[j\]=true;

动态规划的推导公式为

当i=j+1时，T\[i\]\[j\]=(Array\[i\]==Array\[j\]),相邻两元素是否相等

当i>j+1时，需要判断i与j之间的子串是否是回文串,即T\[i\]\[j\]=(Array\[i\]==Array\[j\])&&T\[i+1\]\[j-1\]

PS:状态矩阵赋值过程必须使用左下三角的形式 否则会产生误判 使用了未赋值的位置

### 实现代码： ###

package 课后算法题;
    
    import java.util.Scanner;
    
    public class 最长回文串 {
    
    	public static String MaxHuiWen(String str) {
    		// 非空判断
    		if ((str == null) || str.length() == 0) {
    			return null;
    		}
    		// 将字符串转换为字符数组
    		char[] Array = str.toCharArray();
    		int first = 0;
    		int end = 0;// 当前字符串中回文串的始末位置 包括末位置
    
    		boolean[][] T = new boolean[Array.length][Array.length];
    
    		for (int i = 0; i < Array.length; i++) {
    			for (int j = 0; j <= i; j++) {
    
    				if (i == j) {
    					T[i][j] = true;
    				} else if (j - i == 1) {
    					T[i][j] = (Array[i] == Array[j]);
    				}
    
    				//判断当前是否为回文串 如果是 长度是否大于当前存储的回文串
    				if (T[i][j] && (i - j) > end - first) {
    					first = j;
    					end = i;
    				}
    			}
    		}
    		
    		//将数组转化为字符串返回
    		return String.valueOf(Array, first, end);
    	}
    
    	public static void main(String[] args) {
    		Scanner s = new Scanner(System.in);
    		System.out.print("原字符串：");
    		String str = s.nextLine();
    		System.out.print("最长回文串：");
    		System.out.println(MaxHuiWen(str));
    	}
    }

### 输出结果示例： ###

![20190801174530220.png][]

[20190801174530220.png]: /images/20211109/af6eb346aaff4f5996982342e2eac9be.png