IT博客汇 | [原]LeetCode-- Longest Palindromic Substring

[原]LeetCode-- Longest Palindromic Substring

csharp25发表于 2015-12-02 10:18:23

题目描述：

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

在字符串s中找到最长为回文的子串。

思路：
1.从s[i]开始两边找，依次判断是否为回文，复杂度为O(N^3)，其中，i∈(0,n)无法通过OJ的测试数据。
2.使用dp，其中dp[i,j]表示从s[i]到s[j]是否为回文。复杂度为O(N^2)

实现代码：

public class Solution {
    public string LongestPalindrome(string s)
    {
        if(s.Length == 0 ){
    		return string.Empty;
    	}
    	
    	if(s.Length == 1){
    		return s;
    	}
    	
    	var dp = new bool[s.Length, s.Length];
    	
    	for(var i = 0; i < s.Length; i++)
            {
                for(var j = 0; j < s.Length; j++)
                {  
                    if(i >= j)
                    {
                        dp[i,j] = true;
                    }
                    else
                    {
                        dp[i,j] = false;
                    }
                }
            }
    	
    	var first = 0;
    	var last = 0;
    	var maxLen = 0;
    	
    	for(var i = 1;i < s.Length ; i++){
    		for(var j = 0;j < s.Length - i ; j++){
    			if(s[j] != s[i + j]){
    				dp[j, j + i] = false;
    			}
    			else{
    				dp[j, j + i] = dp[j + 1,j + i - 1];
    				if(dp[j , j + i] && i + 1 > maxLen){
    					first = j ;
    					last = first + i;
    					maxLen = i + 1;
    				}
    			}
    		}
    	}
    	
    	return s.Substring(first , last - first + 1);
	
	
    }
}