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

[5/22] 647. Palindromic Substrings

작성자 정보

  • mingki 작성
  • 작성일

컨텐츠 정보

본문

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

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


647. Palindromic Substrings
Medium
7065161Add to ListShare

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 페이지
게시글 쓰기
번호
제목
이름

최근글


새댓글


Stats


  • 현재 접속자 74 명
  • 오늘 방문자 606 명
  • 어제 방문자 683 명
  • 최대 방문자 1,262 명
  • 전체 회원수 264 명
알림 0