엔지니어 게시판
LeetCode 솔루션 분류

[5/22] 647. Palindromic Substrings

• mingki 작성
• 작성일

• 465 조회
• 3 댓글

본문

[LeetCode 시즌 3] 2022년 5월 22일 문제입니다.

647. Palindromic Substrings
Medium

Given a string `s`, return the number of palindromic substrings in it.

A string is a palindrome when it reads the same backward as forward.

substring is a contiguous sequence of characters within the string.

Example 1:

```Input: s = "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
```

Example 2:

```Input: s = "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".
```

Constraints:

• `1 <= s.length <= 1000`
• `s` consists of lowercase English letters.

댓글 3

나무토끼님의 댓글

• 나무토끼
• 작성일
``````class Solution:
def countSubstrings(self, s: str) -> int:
def palindrome(st, idx):
cnt = 0
for i in range(1, len(st)):
s, e = i - 1, i + idx
while s >= 0 and e < len(st):
if st[s] == st[e]:
cnt += 1
else:
break
s -= 1
e += 1
return cnt
res = palindrome(s, 0) + palindrome(s, 1) + len(s)
return res``````

coderoncruise님의 댓글

• coderoncruise
• 작성일
Expand Around Possible Centers - Even and Odd

``````"""
abc
|
|

"""
class Solution:
def countSubstrings(self, s: str) -> int:
res = 0

for i in range(len(s)):

l = i
r = i

while l >= 0 and r < len(s):
if s[l] == s[r]:
res += 1
l -=1
r += 1
else:
break

l = i
r = i + 1

while l >= 0 and r < len(s):
if s[l] == s[r]:
res += 1
l -=1
r += 1
else:
break

return res
``````

mingki님의 댓글

• mingki
• 작성일
C++
Runtime: 15 ms, faster than 54.90% of C++ online submissions for Palindromic Substrings.
Memory Usage: 7.6 MB, less than 47.94% of C++ online submissions for Palindromic Substrings.
``````class Solution {
public:
int countSubstrings(string s) {
int n = s.size();
int res = n;

vector<vector<bool>> dp(n + 1, vector<bool>(n + 1, false));

for (int i = 0; i < n; ++i) {
dp[i][i] = true;
}

for (int i = 0; i < n - 1; ++i) {
if (s[i] == s[i + 1]) {
dp[i][i + 1] = true;
++res;
}
}

for (int len = 3; len <= n; ++len) {
for (int i = 0, j = i + len - 1; j < n; ++i, ++j) {
if (dp[i + 1][j - 1] && s[i] == s[j]) {
dp[i][j] = true;
++res;
}
}
}
return res;
}
};``````
전체 126 / 1 페이지

• 등록일 13:55
• 등록일 13:17
• 등록일 11:20
• 등록일 06.23
• 등록일 06.23
• 등록일 06.23
• 등록일 06.23
• 등록일 06.23
• 등록일 06.23

새댓글

• 등록자 학부유학생 등록일 06.22
• 등록자 학부유학생 등록일 06.21
• 등록자 Coffee 등록일 06.21
• 등록자 Coffee 등록일 06.21
• 등록자 SVKOREANS 등록일 06.20
• 등록자 학부유학생 등록일 06.20
• 등록자 Coffee 등록일 06.20
• 등록자 키위 등록일 06.20
• 등록자 학부유학생 등록일 06.19
• 등록자 학부유학생 등록일 06.19

Stats

• 현재 접속자 77 명
• 오늘 방문자 617 명
• 어제 방문자 683 명
• 최대 방문자 1,262 명
• 전체 회원수 264 명