python----최장 회신 서브열의 폭력 해법 및 동적 기획 해법

첫 번째: 폭력 해법, 이중순환, o(n^2)

def longestPalindString(ss):
    palindString=""
    max_len=0
    if len(ss)==1:
        return ss
    for i in range(len(ss)):
        for j in range(i+1,len(ss)):
            is_palind=True
            for k in range(i,int((i+j)//2)+1):
                if ss[k]!=ss[j-k+i]:
                    is_palind=False
                    break
            if is_palind and (j-i+1)>max_len:
                max_len=j-i+1
                palindString=ss[i:j+1]
    if palindString=="":
        palindString=ss[0]
    return palindString

if __name__=="__main__":
    ss="babcbad"
    print(longestPalindString(ss))

두 번째: 동적 기획 해법, 시간 복잡도 o(n^2), 공간 복잡도 o(n^2)는 가장 좋은 문제를 추구한다. 먼저 동적 기획의 세 가지 요소를 생각해 본다. 그것이 바로 최우선 서브구조, 경계, 상태 이동 방정식이다. 그 중에서 상태 이동 방정식: f(i, j):s[i]=s[j]i-j<=1f(i, j):s[i]=s[i]=s[j] and f(i+1, j-1)j-i>1이다. 그 중에서 f(i, j)는 s[i:j:j+1]의 회문 직렬 여부를 나타낸다.

def longestPalindString(s):
    k=len(s)
    matrix=[[0 for i in range(k)] for j in range(k)]
    longestString=""
    longestLen=0
    for j in range(0,k):
        for i in range(0,j+1):
            if j-i<=1:
                if s[i]==s[j]:
                    matrix[i][j]=1
                    if longestLen

세 번째 방법: 동적 기획 알고리즘의 최적화 시간 복잡도는 변하지 않고 공간 복잡도를 o(2n)로 낮추어 nlist로 j를 저장하는 상황에서 모든 하위 문자열이 하위 문자열의 로고인지olist로 j-1을 저장하는 상황에서 모든 하위 문자열이 하위 문자열의 로고인지 여부

def longestPalindString(s):
    k = len(s)
    olist = [0] * k  #      n   ，    
    nList = [0] * k  #   
    logestSubStr = ""
    logestLen = 0
    for j in range(0, k):
        for i in range(0, j + 1):
            if j - i <= 1:
                if s[i] == s[j]:
                    nList[i] = 1  #   j  ，  i         
                    len_t = j - i + 1
                    if logestLen < len_t:  #     
                        logestSubStr = s[i:j + 1]
                        logestLen = len_t
            else:
                if s[i] == s[j] and olist[i + 1]:  #  j-i>1 ，  s[i]    s[j]，    j-1 ， i+1          
                    nList[i] = 1  #   j  ，  i         
                    len_t = j - i + 1
                    if logestLen < len_t:
                        logestSubStr = s[i:j + 1]
                        logestLen = len_t
        olist = nList  #       
        nList = [0] * k  #       
    return logestSubStr

if __name__=="__main__":
    ss="babcbad"
    print(longestPalindString(ss))

네 번째 해법:

def helper(ss,l,r):
    while l>=0 and rlen(res):
            res=temp
        temp=helper(ss,i,i+1)
        if len(temp)>len(res):
            res=temp
    return res
if __name__=="__main__":
    ss="abddbc"
    result=longgestCommonStr(ss)
    print(result)