欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【LeetCode】最长回文子串 (字符串,动态规划)

程序员文章站 2022-03-22 08:08:05
...

【LeetCode】最长回文子串 (字符串,动态规划)

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例1:

输入: “babad”
输出: “bab”
注意: “aba” 也是一个有效答案。

示例2:

输入: “cbbd”
输出: “bb”

1.暴力解法

通过三个循环嵌套,前两个循环控制截取字符串的长度与起始点向右的移动,第三个循环是进行字符的回文匹配。所以暴力解法的时间复杂度是O(n的3次方)。

public String longestPalindrome(String s) {
        int len = s.length();
        if(len<2)
            return s;
        
        char c[] = s.toCharArray();
        int maxLen = 0;
        int start = 0;
        
        for(int i=0;i<len;i++) {
            for(int j=i+1;j<len;j++) {
                if(j-i>maxLen&&palindrome(c,i,j)) {
                    maxLen = j-i;
                    start = i;
                }
            }
        }
        
        return s.substring(start,start+maxLen+1);
    }
    
    public boolean palindrome(char c[],int left,int right) {
        while(left<right) {
            if(c[left++]!=c[right--])
                return false;
        }
        return true;
    }

2.中心扩散法

不同于暴力**法是向右的扩散,中心扩散法是以一个或两个字符为中心向它的两边进行扩散,因为此方法只需要两层循环,所以时间复杂度是O(n的2次方)。【要注意的是中心可能是一个字符也有可能是二个字符,如:abccba】

public String longestPalindrome(String s) {
        int len = s.length();
        if(len<2)
            return s;
        
        char c[] =  s.toCharArray();
        int maxLen = 0;
        int start = 0;
        for(int i=0;i<len-1;i++) {
            int odd = expandFC(c,i,i); //中心为一个字符
            int even = expandFC(c,i,i+1); //中心为两个字符
            
            odd = odd>even?odd:even;
            if(odd>maxLen) {
                maxLen = odd;
                start = i - odd/2;
            }
        }
        
     //需要加1是因为substring函数它的计算规则。如取第零位数是s.substring(0,0+1);
        return s.substring(start,start+maxLen+1);
    }
    
    public int expandFC(char c[],int left,int right) {
        while(left>=0&&right<c.length) {
            if(c[left]!=c[right])
                break;
            left--;
            right++;
        }
        return (right-1) - (left+1);
    }

3.动态规划

判断一个字符串是否为回文可以分解成,判断字符串的首尾是否是相等,然后首尾中的子串是否是回文的。所以dp[i][j] = Si==Sj and dp[i+1][j-1](其中的Si和Sj表示的是首尾,dp[i+1][j-1]表示的是首尾中的子串),有时i+1和j-1等于同一个值位置时可以不需要判断这个子串,状态转移公式就可以改成:dp[i][j] = Si= =Sj and (j-i<3 or dp[i+1][j-1])
然后建表填表,注意通过状态转移公式可以看出填表的方向,应该是从先从上到下,然后从左到向,一列一列的去填写。
【LeetCode】最长回文子串 (字符串,动态规划)

动态规划中包含三个重要的概念:【最优子结构】【边界】【状态转移公式】
总结:
不管该子问题以后是否被用到,只要它被计算过,就将其结果填入表中。这就是动态规划法的基本思路。

public static String longestPalindrome(String s) {
		
		boolean DP[][] = new boolean[s.length()][s.length()];
		int maxLen = 0;
		int start = 0;
		for(int i=0;i<s.length();i++)
			DP[i][i] = true;
		
		//循环是顺序是遵循一列一列的填写
		for(int j=1;j<s.length();j++) {
			for(int i=0;i<j;i++) {
				if(s.charAt(i)!=s.charAt(j))
					DP[i][j] = false;
				else {
					if(j-i<3)
						DP[i][j] = true;
					else
						DP[i][j] = DP[i+1][j-1];
				}
				
				if(DP[i][j]&&j-i+1>maxLen) {
					maxLen = j-i;
					start = i;
				}
					
			}
		}
		
		return s.substring(start,start+maxLen+1);
		
		
    }