[Mock] Amazon 8

5. Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

My Answer 1: Wrong Answer (21 / 176 test cases passed.)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        def func(s, p):
            if len(p) > 1 and p[0] == p[-1]:
                return p
            
            if not s:
                return ""
        
            return func(s[1:], p+s[0])
        
        result = ""
        for i in range(len(s)):
            tmp = func(s[i:], "")
            if len(result) < len(tmp):
                result = tmp
        
        if len(result) == 0:
            return s[0]
        
        return result

s[i:] 마다 재귀 돌려서 시작값과 끝값이 같은지 확인

ccc 같은 case는 통과 X

뭔가 재귀를 썼던 거 같은데... 까먹었네요...^^

Solution 1: Accepted (Runtime: 4340 ms - 29.66% / Memory Usage: 21.9 MB - 17.85%)

class Solution:
    def longestPalindrome(self, s: str) -> str:
        
        n = len(s)
        # Form a bottom-up dp 2d array
        # dp[i][j] will be 'true' if the string from index i to j is a palindrome. 
        dp = [[False] * n  for _ in range(n)]
        
        ans = ''
        # every string with one character is a palindrome
        for i in range(n):
            dp[i][i] = True
            ans = s[i]
            
        maxLen = 1
        for start in range(n-1, -1, -1):
            for end in range(start+1, n):             
                # palindrome condition
                if s[start] == s[end]:
                    # if it's a two char. string or if the remaining string is a palindrome too
                    if end - start == 1 or dp[start+1][end-1]:
                        dp[start][end] = True
                        if maxLen < end - start + 1:
                            maxLen = end - start + 1
                            ans = s[start: end+ 1]
        
        return ans

DP 를 써야했다...

모든 s 마다 자기 자신 한 글자는 palindrome 이 되니까 dp[i][i] = True 설정

start 는 맨 뒤에서부터 시작하고, end 는 start 의 오른쪽을 쭉 훑어줌

start 값과 end 값이 같고 그 사이의 값들도 palindrome 이면
(=> if end - start == 1 start, end 딱 두글자만 / or dp[start+1][end-1]: 두글자 이상)

dp = True & maxLen 기반으로 ans update

---

973. K Closest Points to Origin

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

My Answer 1: Accepted (Runtime: 648 ms - 76.28% / Memory Usage: 20.2 MB - 26.78%)

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        distance = {}
        for i in range(len(points)):
            d = sqrt(points[i][0] ** 2 + points[i][1] ** 2)
            distance[i] = d
        
        sd = sorted(distance.items(), key=operator.itemgetter(1))
        
        result = []
        for key, val in sd:
            if len(result) == k:
                return result
            result.append(points[key])
        
        return result

dictionary 에 [index:distance] 형태로 넣어주고 distance 값을 기준으로 정렬
=> sd = sorted(distance.items(), key=operator.itemgetter(1))

순서대로 k 만큼 보면서 result 에 append 해서 return