saurus2
Saurus2
saurus2
전체 방문자
오늘
어제
  • 분류 전체보기
    • 개발
      • AJAX
    • ML Ops
    • Profile
    • 음식점
    • 배낭여행
    • 컴퓨터공학
      • 알고리즘 공부
      • C++
      • Sever 스터디
      • Java spring
      • 알고리즘 _ 문제해결
      • 딥러닝
      • Java 정리
      • Python
      • LeetCode 1000
      • Machine Learning Study
      • Sign language Detection Pro..
      • LeetCode Solutions
    • 비콘
    • 데일리 리포트
    • 유학일기
      • 영어 공부
      • Daily
    • AI Master Degree
      • Data Mining
      • AI and Data engineering
      • Math Foundations for Decisi..
      • Natural Language Processing

블로그 메뉴

  • 홈
  • 태그
  • 미디어로그
  • 위치로그
  • 방명록

공지사항

인기 글

태그

  • 알고리즘문제해결
  • 알고리즘
  • LeetCode
  • 파이썬
  • BFS
  • c++
  • 개발자
  • 리트코드
  • 딥러닝
  • 취업준비
  • 백준
  • DFS
  • 취준
  • 개발자 취업준비
  • 릿코드
  • Python
  • 온라인저지
  • 딕셔너리
  • two pointer
  • 문제해결능력

최근 댓글

최근 글

티스토리

hELLO · Designed By 정상우.
saurus2

Saurus2

컴퓨터공학/LeetCode 1000

[LeetCode] 5. Longest Palindromic Substring

2022. 8. 16. 15:15

5. Longest Palindromic Substring

Medium

Given a string s, return the longest palindromic substring in s.

 

Example 1:

Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:

Input: s = "cbbd"
Output: "bb"

 

Constraints:

  • 1 <= s.length <= 1000
  • s consist of only digits and English letters.

문제 풀이

문제 접근

  1. s 문장의 글자 크기는 1000 이기 때문에 모든 조건을 다 확인해봐도 시간초과가 되지 않을 것 같다. 

풀이

  1. Palindrom 단어는 두가지 케이스가 존재한다.
  2. 가운데 인덱스에서 양쪽으로 퍼지는 경우.
  3. 각 두개 인덱스에서 양쪽으로 퍼지는 경우가 있다. 
  4. 0 부터 문장의 끝까지 모두 검색하면서, 두가지 케이스를 모두 확인한다. 

소스 코드

class Solution:
    def longestPalindrome(self, s: str) -> str:
        self.res_cnt = 0
        self.res = ''
        def check(l, r, s, ans):
            while l >= 0 and r < len(s):
                if s[l] != s[r]:
                    break
                ans += 2
                l -= 1
                r += 1
            if ans > self.res_cnt:
                self.res_cnt = ans
                self.res = s[l + 1 : r]
        for i in range(len(s)):
            check(i - 1, i + 1, s, 1)
            check(i, i + 1, s, 0)
        return self.res
저작자표시 (새창열림)

'컴퓨터공학 > LeetCode 1000' 카테고리의 다른 글

[LeetCode] 49. Group Anagrams  (0) 2022.08.17
[LeetCode] 804. Unique Morse Code Words  (0) 2022.08.17
[LeetCode] 387. First Unique Character in a String  (0) 2022.08.16
[LeetCode] 13. Roman to Integer  (0) 2022.08.16
[LeetCode] 90. Subsets II  (0) 2022.08.14
    '컴퓨터공학/LeetCode 1000' 카테고리의 다른 글
    • [LeetCode] 49. Group Anagrams
    • [LeetCode] 804. Unique Morse Code Words
    • [LeetCode] 387. First Unique Character in a String
    • [LeetCode] 13. Roman to Integer
    saurus2
    saurus2
    Simple is Best

    티스토리툴바