1048. Longest String Chain

https://leetcode.com/problems/longest-string-chain/

Longest String Chain - LeetCode

 

DP문제

 

가장 긴 스트링 체인의 길이를 리턴하는 문제이다.

 

리스트를 길이 순으로 먼저 정렬해야한다.

sorted(words, key = len) 사용가능.

 

정렬 전

[ czvh, gru, gr, kss, gruj, ks, zczvh, kssq ]

 

정렬 후

[ ks, gr, gru. kss, kssq, czvh, gruj, zczvh ]

 

dp dictionary 정의가 필요

key(스트링값) : value( 스트링 체인의 길이 )

 

모든 단어에 대해서

가능한 predecessor를 생성한다. 만약 zczvh가 단어라면

czvh, zzvh, zcvh, zczh, zczv 총 다섯가지 경우를 생성이 가능하다 (알파벳 한개씩 제거된 단어)

 

dp 딕셔너리에 이미 값이 존재하면,

이미 그 스트링 체인의 길이를 계산한 것으로 이해가 가능.

존재하면 스트링 체인 연결이 가능하므로 1을 더해주면 된다.

 

 

class Solution(object):
    def longestStrChain(self, words):
        """
        :type words: List[str]
        :rtype: int
        """
        
        sorted_list = sorted(words, key = len)
        
        for w in sorted_list:
        
        	max_length = 0
        	for i in range(len(w)):
            
            	predecessor = w[:i] + w[i+1:]
                
                max_length = max(max_length, dp.get(predecessor, 0) + 1)
            dp[w] = max_length
           
        return max(dp.values())
            	
            	
        
        

 

 

 

https://leetcode.com/problems/longest-string-chain/discuss/428354/Python-2-Approaches%3A-DFS-%2B-Memo-DP-with-complexity-analysis