Java---Show my easy understanding solution!


  • 0
    B
    public class Solution {
        /*
     *  动态规划法
     *  比如P[i,j](表示以i开始以j结束的子串)是回文字符串,那么P[i+1,j-1]也是回文字符串
     *  P[i,j]=false 表示子串[i,j]不是回文串。P[i,j]=true 表示子串[i,j]是回文串。
     *  初始化 P[i,i]=1;
     *         |- P[i+1, j-1], if(s[i]==s[j])
     *  P[i,j]=|
     *  	   |_ false, if(s[i]!=s[j])
     */
    public static String longestPalindrome1(String s) {
    	int maxLen = 0;
    	int start = 0;
    	boolean[][] P = new boolean[50][50];
    	if(s.length()==1)
    		return s;
    	//初始化
    	for(int i = 0;i<s.length();i++){
    		P[i][i] = true; //P[i][j]表示以i开始,以j结束的子串
    		if(i<s.length()-1&&s.charAt(i)==s.charAt(i+1)){
    			P[i][i+1] = true;
    			start = i;
    			maxLen = 2;
    		}
    	}
    	for(int len = 3;len<=s.length();len++){ //长度从3开始
    		for(int i = 0;i<=s.length()-len;i++){ //设置初始位置
    			int j = i+len-1;  //与i相对的位置
    			//若在两端的位置i,j位置处的字符相等,再者从i+1~j-1之间为true,更新
    			if(P[i+1][j-1]==true&&s.charAt(i)==s.charAt(j)){
    				P[i][j] = true;
    				maxLen = len;
    				start = i;
    			}
    		}
    	}
    	//System.out.println("start: "+start+" maxLen:"+maxLen);
    	if(maxLen>=2)
    		return s.substring(start, start+maxLen);
    	return null;
    }
    

    }


  • 0
    Y

    doesn't work for "avc"
    and
    complexity too high


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.