palindromic
-
5. Longest Palindromic SubstringProgramming/leetcode 2021. 1. 25. 15:30
문자열의 부분중 가장 긴 회문 찾기 문제이다. Dynamic Programming(이하 DP)으로 많이 풀지만, 이번에는 window sliding기법을 이용해서 풀어보자. 사실 DP로 푸는 것은 잘 이해가 되지 않았다.. 더보기 Input: s = "babad" Output: "bab" Note: "aba" is also a valid answer. 아이디어는 이렇다. 현재 위치를 중심으로 양 옆을 늘려가면서 회문인지 확인하는 것이다. ex) 'abac'에서 위치를 찾아보자. 두번째 'b'의 위치에서 보자 b를 중심으로 양 옆에 'a'가 있고, 'aba'는 회문이 된다. 하지만 이 아이디어에서 조심해야될것이 중심을 홀수, 짝수를 구분해야된다는 것이다. 이유는 홀수, 짝수 일때 중심이 달라지기때문이다. ..