오늘 배웠습니다: 가장 긴 회문 부분 문자열

문제 설명



문자열을 받아 가장 긴 회문 부분 문자열을 반환하는 함수를 작성하십시오.

샘플 입력



string = "qazaasdffdsaawsx"

샘플 결과



"aasdffdsaa"

코드 #1



def longest_palindromic_substring(string):
    cur_longest = [0, 1]
    for idx in range(1, len(string)):
        odd = get_longest_palindrome(string, idx - 1, idx + 1)
        even = get_longest_palindrome(string, idx - 1, idx)
        longest = max(odd, even, key=lambda x: x[1] - x[0])
        cur_longest = max(longest, cur_longest, key=lambda x: x[1] - x[0])
    return string[cur_longest[0]:cur_longest[1]]


def get_longest_palindrome(string, idx_l, idx_r):
    while idx_l > -1 and idx_r < len(string):
        if string[idx_l] != string[idx_r]:
            break
        idx_l -= 1
        idx_r += 1
    return [idx_l + 1, idx_r]


메모


  • 거울에서 부분 문자열을 보는 것과 같은 회문 문제를 상상해보십시오.
  • 거울은 캐릭터 사이("abba") 또는 캐릭터 자체("aba")에 있을 수 있습니다.
  • 순진한 접근 방식: 길이 2에서 문자열 길이까지 가능한 모든 하위 문자열 조합을 생성한 다음 check_palindrome 기능을 적용합니다.

  • 크레딧


  • 문제 진술에 대한 Algoexpert.
  • 표지 이미지의 최수현( https://unsplash.com/photos/ZUS1xCxoQCA ).
  • 좋은 웹페이지 즐겨찾기