BruteForce ⭕
가능한 모든 시작점에서, 모든 길이에 대해 팰린드롬인지 확인
class Solution {
fun longestPalindrome(s: String): String {
for (len in s.length downTo 1) {
for (start in 0..s.length-len) {
val palindrome = s.substring(start, start + len)
if (isPalindrome(palindrome)) return palindrome
}
}
return ""
}
}
// 주어진 문자가 팰린드롬인지 판단
fun isPalindrome(s: String): Boolean {
var left = 0
var right = s.length-1
// 양끝에서 투 포인터 탐색
while (s[left] == s[right] && left < right) {
left++
right--
}
return (left >= right)
}
시간 복잡도: 문자 순회(시작점) X 가능한 길이 X 팰린드롬 판단 = n^3
모든 idx를 팰린드롬의 중앙으로 두고, 최장길이 비교 1에서는 시작점을 기준으로 특정 길이로 문자를 슬리이싱한 후, 해당 문자가 팰린드롬인지 판단(양끝 → 중간 투포인터 탐색)했음 ⇒ 중복되는 탐색 존재
→ 팰린드롬은 중간 기준을 중심으로 좌우 대칭
→ 팰린드롬 판단에 투포인터 탐색 사용
→ 탐색 시작점을 팰린드롬의 중간점으로 두고 최장 길이 구하기(중간 → 양끝 투포인터 탐색)로 탐색을 한번 줄일 수 있음
class Solution {
fun longestPalindrome(s: String): String {
var answer = ""
for (i in s.indices) {
val l1 = isPalindrome(i, i, s) // 가운데 값이 있는 경우 -> 전체 길이 홀수
val l2 = isPalindrome(i, i+1, s) // 가운데 값이 없는 경우 -> 전체 길이 짝수
if (l1 >= l2 && l1 > answer.length) {
answer = s.substring(i - (l1/2), i + (l1/2) + 1)
} else if (l1 < l2 && l2 > answer.length) {
answer = s.substring(i - (l2/2) + 1, i + (l2/2) + 1)
}
}
return answer
}
// 주어진 문자열[s:e]에서 가장 긴 팰린드롬의 길이 리턴
fun isPalindrome(s: Int, e: Int, str: String): Int {
var left = s
var right = e
var len = 0
// 시작지점에서 양 끝으로 투 포인터 탐색
while (left >= 0 && right < str.length && str[left] == str[right]) {
len = right - left + 1
left--
right++
}
return len
}
}
시간 복잡도: 문자 순회(시작점) X 팰린드롬 최장길이 탐색 = n^2
