LeetCode 솔루션

[5/22] 647. Palindromic Substrings

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.05.22 15:42

7,290 조회
3 댓글
0 추천
0 비추천
목록 게시글 쓰기

[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.

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.

#LeetCode, #Facebook, #Twitter, #Expedia, #Google, #Microsoft, #Amazon, #Uber, #Salesforce, #Goldman Sachs, #Docusign, #Walmart Global Tech, #Bloomberg, #SAP, #ByteDance, #LinkedIn, #String, #Dynamic Programming(DP)

링크

https://leetcode.com/problems/palindromic-substrings/ 3266 회 연결

익명
작성일 2022.05.22 16:31

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

익명
작성일 2022.05.22 23:19

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

익명
작성일 2022.05.24 13:55

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;
    }
};