Python에서 가장 긴 감소하는 단어 체인의 길이를 찾는 프로그램은 무엇입니까?

<시간/>

유효한 단어 목록이 있고 문자열 s도 있다고 가정하면 s에서 시작하여 단일 문자를 제거하고 여전히 유효한 단어를 만들 수 있는 가장 긴 감소 단어 체인의 길이를 찾아야 합니다.

따라서 입력이 단어 =["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"] s ="limit"인 경우 "limit", "limit" ->"limi" -> "lii" -> "li"라는 단어로 시작하여 체인을 만들 수 있으므로 출력은 4가 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다.

solve() 함수를 정의합니다. 이것은 단어가 필요합니다, s
max_num :=0
단어의 각 i에 대해 수행
- i가 s와 같으면
  - 범위 0에서 s까지의 j에 대해 다음을 수행합니다.
    - max_num :=최대값 1 + solve(words, s[인덱스 0에서 j-1]연결 s[인덱스 j + 1에서 끝까지]) 및 max_num
반환 max_num

예

class Solution:
   def solve(self, words, s):
      max_num = 0
      for i in words:
         if i == s:
            for j in range(len(s)):
               max_num = max(1 + self.solve(words, s[:j] + s[j + 1 :]), max_num)
      return max_num

ob = Solution()
words = ["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"]
s = "limit"
print(ob.solve(words, s))

입력

["lii", "limit", "limi", "li", "coffee", "jug", "pool", "type"],"limit"