[PYTHON] Let Code Day51 Starting from Zero "647. Palindromic Substrings"

Overview

It seems that coding tests are conducted overseas in interviews with engineers, and in many cases, the main thing is to implement specific functions and classes according to the theme.

As a countermeasure, it seems that a site called Let Code will take measures.

A site that trains algorithmic power that can withstand coding tests that are often done in the home.

I think it's better to have the algorithm power of a human being, so I'll solve the problem irregularly and write down the method I thought at that time as a memo.

Leetcode

Leet Code Table of Contents Starting from Zero

Last time Leet Code Day 50 "739. Daily Temperatures" starting from zero

Right now, I'm prioritizing the Medium of the Top 100 Liked Questions. I solved all Easy, so if you are interested, please go to the table of contents.

Twitter I'm doing it.

problem

647. Palindromic Substrings The difficulty level is Medium. Excerpt from Top 100 Liked Questions.

The problem is that the string s is given. Implement an algorithm that counts the number of palindromes in this string and returns that number.

Substrings with different start or end indexes are counted as different substrings even if they are composed of the same character.

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

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

solution

As a common palindrome check method, if the one that licked the character string from the beginning and the one that licked from the opposite match match, it means that it is a palindrome.

If Bruteforce (brute force) is fine, you can double the for statement, but if you double the for statement, the amount of calculation will be O (N ^ 2), which will be very slow. I will.

class Solution:
    def countSubstrings(self, s: str) -> int:
        ans = 0
        if not s:
            return ans
        for i in range(len(s)):
            ans += 1 
            for j in range(1, i+1):
                if self.is_palindrom(s[i-j:i+1]):
                    ans += 1
        return ans

    def is_palindrom(self, s):
        return s == s[::-1]
# Runtime: 604 ms, faster than 13.54% of Python3 online submissions for Palindromic Substrings.
# Memory Usage: 13.8 MB, less than 81.86% of Python3 online submissions for Palindromic Substrings.

Let's take a look at the discussion to see what other solutions are available. For example, [this solution](https://leetcode.com/problems/palindromic-substrings/discuss/392119/Solution-in-Python-3-(beats-~94)-(six-lines)-(With- Detaiiled-Explanation)).

class Solution:
    def countSubstrings(self, s: str) -> int:
	    L, r = len(s), 0
	    for i in range(L):
	    	for a,b in [(i,i),(i,i+1)]:
	    		while a >= 0 and b < L and s[a] == s[b]: a -= 1; b += 1
	    		r += (b-a)//2
	    return r
# Runtime: 132 ms, faster than 71.16% of Python3 online submissions for Palindromic Substrings.
# Memory Usage: 13.8 MB, less than 71.36% of Python3 online submissions for Palindromic Substrings.		

The conditioning part of the while statement is the key. I thought it was amazing to be able to think about the flow firmly without omissions and duplication like this.

It is easy to understand at first glance, and although it is in English, it explains in detail, so if you are interested, you may want to check it at the link.

That's all for today. Thank you for your hard work.