[LeetCode] 1048 | Longest String Chain | Python

---

문제 링크: https://leetcode.com/problems/longest-string-chain/

---

문제

You are given an array of words where each word consists of lowercase English letters.

wordA is a predecessor of wordB if and only if we can insert exactly one letter anywhere in wordA without changing the order of the other characters to make it equal to word_B.

• For example, "abc" is a predecessor of "abac", while "cba" is not a predecessor of "bcad".

A word chain is a sequence of words [word1, word2, ..., wordk] with k >= 1, where word1 is a predecessor of word2, word2 is a predecessor of word3, and so on. A single word is trivially a word chain with k == 1.

Return the length of the longest possible word chain with words chosen from the given list of words.

---

조건

• 1 <= words.length <= 1000
• 1 <= words[i].length <= 16
• words[i] only consists of lowercase English letters.

---

내 풀이

프로그래밍 문제를 풀 때, 무언가 더하는 문제는 항상 빼는 방식으로 생각하면 더 간단할 때가 있다.

이 문제도 그런 방식으로 생각한다.

또한 DP를 사용한다.

예를 들면 ['a', 'ab']가 있을 때, 'a'는 무조건 1이고, 'ab'는 'a'로 만들기 때문에 2가 된다.

이런 것을 DP로 구현한다.

---

코드

class Solution:
    def longestStrChain(self, words: List[str]) -> int:
        words.sort(key=len)
        ans = defaultdict(int)
        
        for word in words:
            print(word)
            ans[word] = 1
            for pos in range(len(word)):
                smaller = word[:pos] + word[pos+1:]
                
                if smaller in words:
                    ans[word] = max(ans[word], ans[smaller] + 1)
                    
        return max(ans.values())