(Leetcode) 647 - Palindromic Substrings 풀이
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
https://leetcode.com/problems/palindromic-substrings/description/
내가 작성한 풀이
Longest Palindromic Substring 문제를 풀어본 적이 있다면 보너스 문제같은 느낌이다. (문제, 풀이) 약간만 수정해주면 바로 풀린다.
포인터 i를 이용하여 각 위치에서의 palindromic substring 을 모두 계산해주면 된다.
class Solution {
public int countSubstrings(String s) {
int count = 0;
char[] charArray = s.toCharArray();
for (int i = 0; i < s.length(); i++) {
char currentChar = charArray[i];
count++;
int left = i;
int right = i;
while (right < s.length() - 1 && currentChar == charArray[right + 1]) {
right++;
count++;
}
while (left > 0 && right < s.length() - 1 && charArray[left - 1] == charArray[right + 1]) {
left--;
right++;
count++;
}
}
return count;
}
}
TC, SC
시간 복잡도는 평균적으로 O(n)이다. palindrome 의 길이가 n 에 가까워질수록 시간 복잡도는 O(n^2) 에 가까워 진다. 공간 복잡도는 O(n)이다.