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 42 "2. Add Two Numbers" starting from zero

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

Twitter I'm doing it.

problem

5. Longest Palindromic Substring

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

Given the string s, design an algorithm that finds the longest palindrome in that string (whichever you read is the same).

Input: "babad" Output: "bab" Note: "aba" is also a valid answer.

Input: "cbbd" Output: "bb"

Solved before Leet Code Day 30 starting from zero "234. Palindrome Linked List" It's similar to this, but last time it only checked whether the given linked list was a palindrome, but this time it changed to extracting the longest one from it as a string. It's a little complicated.

solution

However, the orthodox idea of the palindrome problem is to compare the original element with the one that licks the element upside down like the last time, and if it matches, continue the comparison, otherwise It would be to save those strings in the prepared strings.

For example, the " babad " given as an example

babad When dabab Licking together from the front, leaving the longer element compared to the length of the originally saved string from the first ʻa to the second ʻa that match, and finally It seems that it can be solved by returning the character string to. The question is how to set how to lick that element, but inversion can be easily implemented with the slice [:: -1]. So, it will be O (N ^ 2), but let's solve it with the rough technique of turning the for statement twice.

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if not s:
            return ""
        for i in range(len(s),0,-1):
            for j in range(len(s)-i+1):
                if s[j:i+j] == s[j:i+j][::-1]:
                    return s[j:i+j]
# Runtime: 4884 ms, faster than 25.37% of Python3 online submissions for Longest Palindromic Substring.
# Memory Usage: 13.7 MB, less than 22.69% of Python3 online submissions for Longest Palindromic Substring.

It's too late ...

Some examples of insanely fast answers were:

class Solution(object):
    def longestPalindrome(self, s: str) -> str:
        if len(s) < 2:
            return s
        start = 0
        maxLen = 1
        i = 0

        while i < len(s):
            l = i
            r = i
            while r < len(s) - 1 and s[r] == s[r+1]:
                r += 1
            i = r + 1
            while r < len(s)-1 and l > 0 and s[r+1] == s[l-1]:
                l -= 1
                r += 1
            if maxLen < r - l + 1:
                start = l
                maxLen = r - l + 1
        return s[start: start + maxLen]
# Runtime: 116 ms, faster than 95.05% of Python3 online submissions for Longest Palindromic Substring.
# Memory Usage: 13.8 MB, less than 22.69% of Python3 online submissions for Longest Palindromic Substring.

https://leetcode.com/problems/longest-palindromic-substring/discuss/410963/Python-beats-93-solution-with-illustrations

Sugge fast! !! !! !! !! There is no end to what you have to study. very good.

So that's it for this time. Thank you for your hard work.

[PYTHON] Let Code Day 43 "5. Longest Palindromic Substring" Starting from Zero

Overview

problem

solution