LeetCode 솔루션 분류
[5/22] 647. Palindromic Substrings
본문
[LeetCode 시즌 3] 2022년 5월 22일 문제입니다.
https://leetcode.com/problems/palindromic-substrings/
647. Palindromic Substrings
Medium
7065161Add to ListShareGiven a string s
, return the number of palindromic substrings in it.
A string is a palindrome when it reads the same backward as forward.
A 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님의 댓글
- 익명
- 작성일
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님의 댓글
- 익명
- 작성일
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.
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;
}
};