Question 1048. Longest String Chain

Link:

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

My Code:

class Solution:
    def longestStrChain(self, words: List[str]) -> int:

        def PredCheck(OldString, NewString):
            if len(OldString) != (len(NewString)-1):
                return False
            else:
                for j in range(len(NewString)):
                    CheckStr = NewString[0:j]+NewString[j+1:len(NewString)]
                    if CheckStr == OldString:
                        return True
                return False
        
        #We need to sort the string list based on the length of the strings in the list
        #for i in range(1,len(words)):
           # NewList = []
          #  for j in range(len(words)):
         #       NewString = words[j]
        #        Max = 0
       #         for k in range(len(words)):
      #              OldString = words[k]
     #               if PredCheck(OldString,NewString):
    #                    Max = max(ResultList[i-1][k], Max)
   #             Value = Max+1
  #              NewList.append(Value)
 #           ResultList.append(NewList)
#        return max(ResultList[-1])
        
        NewWords = sorted(words,key = len)
        ResultList = [1]
        for i in range(1,len(NewWords)):
            NewString = NewWords[i]
            Max = 0
            for j in range(i):
                OldString = NewWords[j]
                if PredCheck(OldString,NewString):
                    Max = max(ResultList[j],Max)
            Value = Max+1
            ResultList.append(Value)
        return max(ResultList)

Explanation:

The idea of the code is following this: The matrix Mat[i][j] means the maximum string chain we may get if we can only choose i elements at most and ending element must be words[j]. The commented code is the original code. It has a time complexity of n^3. However, we may improve it, as we may notice that the order of the element in the list should not change the result. Hence we may first sort the string list by the length of the element. Then we may use one dimensional list to store the result .Here ResultList[i] means the maximum number of the string if the ending element is NewWords[i] (Sorted string list). We do not to apply n^2 check scheme as based on the sorted string list, all the possible predecessor given string NewWord[i] are included in the NewWords[k], 0<=k<i-1. Hence we just need to check with n^2 time complexity. The sort scheme (usually) has a complexity of n^2, hence the total time complexity of the code is n^2