[LeetCode] 647. Palindromic Substrings

문제

https://leetcode.com/problems/palindromic-substrings/description/

 

입력

s: String = 문자열 

1 <= s.count <= 1000

결과

ans: Int = s의 부분 문자열에서 찾을 수 있는 모든 회문 개수

해석

회문이란 중심을 기준으로 대칭되는 문자열이다. 

 

크게 두가지 종류가 있다. 

 

1. 홀수 문자열 회문
   • abcba 
   • 중심을 기준으로 정확히 대칭
   • 왼쪽 포인터와 오른쪽 포인터가 c를 기준으로 출발하면 됨 
2. 짝수 문자열 회문
   • abccba
   • 중심이 딱 보이지는 않음
   • 왼쪽 포인터는 2번 index , 오른쪽 포인터는 3번인덱스를 기준으로 출발하면 됨
   • 즉 중심이 2개 

그렇기 때문에 중심을 하나씩 움직이며 각 기준의 홀수 회문과 짝수 회문을 모두 더해가면 s의 부부 문자열의
모든 회문을 찾을 수 있다. 

 

코드

import Foundation 

class Solution {

    func countSubstrings(_ s: String) -> Int {
        let s = Array(s)
        let n = s.count
        
        func countPalindromes(left l : Int, right r: Int) -> Int {
            var count: Int = 0
            var l = l
            var r = r
            
            while 0 <= l && r < n && s[l] == s[r] {
                count += 1 
                l -= 1 
                r += 1 
            } 

            return count 
        }

    var answer: Int = 0

    for center in 0..<n {

        // 첫 left 와 right가 같다는건 홀수길이의 회문 검사  aba 같은 경우 
        answer += countPalindromes(left: center, right: center)

        // 다르게 시작하면 짝수길이의 회문 검사 abab 같은 경우 
        answer += countPalindromes(left: center, right: center+1)

    }

    return answer    

    }
}