substring (2) 썸네일형 리스트형 [Leetcode] 647번 - palindromic substring 문제 링크: https://leetcode.com/problems/palindromic-substrings/1. 문제 파악문제를 나눠서 정의: 주어진 문자열의 substring 중에서 좌우 대칭되는 개수 구하기주어진 문자열에서 좌우 대칭되는 substring 찾기좌우 대칭되는 substring을 카운트 하기시간잡도 파악: 1 범위로 보아 시간복잡도는 O(N^2) 일것으로 예상 2. 핵심 문제 풀이 도출문제를 나눈것에 대해 풀이를 도출해본다.좌우 대칭되는 문자열의 중앙값부터 시작해서 양쪽으로 이동하면서 문자가 일치/불일치를 판단 -> 불일치될때까지 반복하면 대칭되는 문자열을 찾을수 있다. -> O(N)모든 substring중에서 좌우 대칭되는 것을 카운팅해야되기 때문에, 모든 문자를 중앙값으로 두고 좌.. [Leetcode] 5번 - 최대길이 palindromic 부분 문자열 문제 링크: https://leetcode.com/problems/longest-palindromic-substring/description/1. 문제 파악문제를 나눠서 정의: 주어진 문자열의 substring 중에서 대칭되는 것중에서 가장 긴것 찾기주어진 문자열에서 좌우 대칭되는 substring 찾기좌우 대칭되는 substring 중에서 제일 긴 것 찾기시간복잡도 파악: 1 범위로 보아 시간복잡도는 O(N^2) 일것으로 예상2. 핵심 문제 풀이 도출문제를 나눈것에 대해 풀이를 도출해본다.좌우 대칭되는 문자열의 중앙값 부터 시작해서 양쪽으로 이동하면서 문자가 일치/불일치를 판단 -> 불일치될때까지 반복하면 대칭되는 문자열을 찾을수 있다. -> O(N)모든 substring에서 가장 긴 좌우 대칭 문.. 이전 1 다음