[LeetCode] 2370. Longest Ideal Subsequence

접근

• O(N^2) 으로 처음에 시도했다가 TLE에 걸렸음
• 알파벳의 갯수와 k를 활용하여 이에 적합한 솔루션을 짜는 것이 핵심
• 문제를 제대로 이해한다면 올바른 솔루션을 짜는 것이 가능하니.. 문제를 정확히 이해할 것...

 

문제 링크

https://leetcode.com/problems/longest-ideal-subsequence/description/

 

시도1(TLE)

O(N^2) 으로 모두 비교하는 방법으로 처음 솔루션을 작성했습니다. 하지만 이 시도는 TLE에 걸려 통과하지 못했습니다.

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        s_length = len(s)
        DP = [1 for _ in range(s_length)]

        for i in range(s_length):
            for j in range(i):
                tmp = ord(s[i])-ord(s[j])
                if abs(tmp) <= k:
                    DP[i] = max(DP[j]+1, DP[i])

        return max(DP)

 

솔루션

부연 설명 : k번째 앞에서부터 k번째 뒤의 알파벳이 탐색 중인 알파벳의 subsequence로 포함될 수 있습니다. 이러한 성질을 이용해서 탐색을 완료하면 알파벳들 중, 가장 큰 값이 답이 됩니다. 알파벳과 k범위를 통해 창의적인 접근이 필요합니다.

class Solution:
    def longestIdealString(self, s: str, k: int) -> int:
        DP = [0 for _ in range(26)]
        
        for v in s:
            index = ord(v) - ord("a")
            max_value = DP[index]

            for j in range(max(0, index-k), min(26, index+k+1)):
                max_value = max(DP[j], max_value)
            DP[index] = max_value + 1

        return max(DP)