首页 > itarticle > longest palindromic substring – leetcode a5

longest palindromic substring – leetcode a5

admin 11月 12, 2020 0

Problem

Problem description
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: “babad”

Output: “bab”

Note: “aba” is also a valid answer.

Analysis

  • Dynamic programming, O(n^2)
  • s[i..j] is a palindromic substring iff s[i+1..j-1] is and s[i] == s[j]

Python Implementation

  • Complexity: O(n^2)
  • Time limit exceeded
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    		 
    class :
    	def longestPalindrome(self, s):
    		"""
    		:type s: str
    		:rtype: str
    		"""
    		f = [[ False for i in range(len(s) + 1)] for i in range(len(s))]
    		for i in range(len(s)):
    			f[i][1] = True
    			f[i][0] = True
    		ans = 1
    		ansi = 0
    		lens = len(s)
    		for L in range(2, lens+1):
    			for i in range(0, lens + 1 - L):
    				if (s[i] == s[i+L-1]):
    					f[i][L] = f[i+1][L-2]
    					if (f[i][L]):
    						ans = L
    						ansi = i
    		return s[ansi: ansi + ans]

C++ Implementation

  • Complexity: O(n^2)
  • Accepted
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    		 
    #include <string>
    #include <cstring>
    using namespace std;
    class Solution {
    public:
        string longestPalindrome(string s) {
            int f[1000][1005];
            memset(f, 0, sizeof(f));
            int n = s.length();
            for (int i = 0; i < n; i++)
            	f[i][0] = f[i][1] = 1;
            int ans = 1;
            int ansi = 0;
           	for (int L = 2; L <= n; L++) {
           		for (int i = 0; i <= n - L; i++){
           			if (s[i] == s[i + L -1])
           				f[i][L] = f[i+1][L-2];
           			if (f[i][L]){
           				ans = L;
           				ansi = i;
           			}
           		}
           	}
           	return s.substr(ansi, ans);
        }
    };
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能