[LeetCode] Palindromic Substrings

Palindrome string은 뒤집었을 때에도 같은 순서를 갖고 있는 문자열이다. 우리말로는 '회문'이라고 한다. palindrome을 가지고 다양한 문제를 만들어낼 수 있는데, 문자열 뿐만 아니라 연결리스트 등 다양한 자료구조의 기본지식을 판단할 수 있는 문제이다. 해당 문제는 부분 문자열에서 palindrome을 찾는 문제였다.

 

class Solution:
    def countSubstrings(self, s: str) -> int:
        
        result = 0
        for length in range(1, len(s) + 1):
            idx_start = 0
            idx_end = length
            
            while idx_end <= len(s):
                now_string = s[idx_start:idx_end]
                if now_string == now_string[::-1]:
                    result += 1
                idx_start += 1
                idx_end += 1
            
        return result

 

단순하게 생각해서 길이 별로 모든 부분 문자열을 생성해내고(시작 인덱스가 다르다면 중복을 허용) 문자열을 뒤집어서 원래 문자열과 같은지 확인하면 된다. 이런 문제를 접근할 때 항상 인덱스를 계산하는게 어렵게 느껴져 기록을 해봤다. 또 이렇게 접근하기 전 O(N^2)으로 풀릴지 확인해봐야 하는데, 입력이 1000밖에 되지 않아 이 방법으로 해결했다.