You are given an array of words where each word consists of lowercase English letters.
word_{A} is a predecessor of word_{B} if and only if we can insert exactly one letter anywhere in word_{A} 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 [word_{1}, word_{2}, ..., word_{k}] with k >= 1, where word_{1} is a predecessor of word_{2}, word_{2} is a predecessor of word_{3}, 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.
Example 1:
Input:
n = 6
words = ["a","b","ba","bca","bda","bdca"]
Output:
4
Explanation:
One of the longest word chains is ["a","ba","bda","bdca"].
Example 2:
Input:
n = 2
words = ["abcd","dbqca"]
Output:
1
Explanation:
The trivial word chain ["abcd"] is one of the longest word chains.
Your Task:
You don't need to read input or print anything. Your task is to complete the function longestChain() which takes integer n and an array of words and returns the size of longest possible word chain.
Expected Time Complexity: O( n * n * L),where L is the length of the longest string in the words.
Expected Space Complexity: O(n)
Constraint:
1 <= n <= 1000
1 <= words[i].length <= 16
 words[i] only consists of lowercase English letters.

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: #User function Template for python3



class Solution:

    def longestChain(self, N, words):

        # Code here

Solutions:
class Solution:

	def longestChain(self, N, words):

		def comp(x, y):
			if len(x) != len(y) + 1:
				return False
			(f, s) = (0, 0)
			while f < len(x):
				if s < len(y):
					if x[f] == y[s]:
						f += 1
						s += 1
					else:
						f += 1
				else:
					f += 1
			if f == len(x) and s == len(y):
				return True
			return False
		dp = [1 for i in range(N)]
		maxi = 1
		words = sorted(words, key=len)
		for i in range(1, N):
			for j in range(i):
				if comp(words[i], words[j]) and 1 + dp[j] > dp[i]:
					dp[i] = 1 + dp[j]
					if maxi < dp[i]:
						maxi = dp[i]
		return maxi


class Solution:

	def longestChain(self, n, arr):

		def compareword(s1, s2):
			if len(s1) != len(s2) + 1:
				return False
			first = second = 0
			while first < len(s1):
				if second < len(s2) and s1[first] == s2[second]:
					first += 1
					second += 1
				else:
					first += 1
			if first == len(s1) and second == len(s2):
				return True
			return False
		arr = sorted(arr, key=len)
		dp = [1] * n
		maxi = 1
		for i in range(n):
			for prev in range(i):
				if compareword(arr[i], arr[prev]) and dp[prev] + 1 > dp[i]:
					dp[i] = 1 + dp[prev]
			if dp[i] > maxi:
				maxi = dp[i]
		return maxi


class Solution:

	def wordchain(self, ch, word):
		l = len(ch)
		r = len(word)
		if r - l != 1:
			return 0
		nope = 0
		j = 0
		for i in range(r):
			if j < l and word[i] == ch[j]:
				j += 1
			else:
				nope += 1
		if nope == 1:
			return 1
		else:
			return 0

	def gen(self, n, words, pos, ch):
		if pos == n:
			return 0
		l = 0
		if self.wordchain(ch, words[pos]):
			l = 1 + self.gen(n, words, pos + 1, words[pos])
		r = self.gen(n, words, pos + 1, ch)
		return max(l, r)

	def longestChain(self, n, words):
		dp = []
		for i in range(n):
			dp.append(1)
		words.sort(key=lambda x: len(x))
		for i in range(n):
			maxi = 0
			for j in range(i):
				if dp[j] > maxi and self.wordchain(words[j], words[i]):
					maxi = dp[j]
			dp[i] = maxi + 1
		return max(dp)


class Solution:

	def longestChain(self, N, words):
		words.sort(key=lambda x: len(x))
		dp = [1 for i in range(N)]
		for i in range(N):
			for j in range(i):
				if self.check(words[j], words[i]) and dp[i] < 1 + dp[j]:
					dp[i] = 1 + dp[j]
		count = 0
		for i in range(len(dp)):
			count = max(count, dp[i])
		return count

	def check(self, s1, s2):
		n = len(s1)
		m = len(s2)
		i = 0
		j = 0
		if n + 1 != m:
			return False
		while i < m:
			if j < n and s2[i] == s1[j]:
				i += 1
				j += 1
			else:
				i += 1
		return i == m and j == n


from collections import defaultdict

class Solution:

	def longestChain(self, n, words):
		n = len(words)
		words.sort(key=lambda w: len(w))
		graph = defaultdict(set)
		for i in range(n):
			word = words[i]
			for j in range(len(word)):
				graph[word[:j] + word[j + 1:]].add(i)
		dists = [1] * n
		ans = 1
		for u in range(n):
			for v in graph[words[u]]:
				dists[v] = max(dists[v], dists[u] + 1)
				ans = max(ans, dists[v])
		return ans


class Solution:

	def longestChain(self, N, words):
		dp = {}
		res = 1
		for word in sorted(words, key=len):
			dp[word] = 1
			for i in range(len(word)):
				prev = word[:i] + word[i + 1:]
				if prev in dp:
					dp[word] = dp[prev] + 1
					res = max(res, dp[word])
		return res


class Solution:

	def longestChain(self, N, words):
		words.sort(key=lambda x: len(x))
		dp = [1] * N
		for i in range(N):
			for j in range(i):
				if self.checkPossible(words[j], words[i]) and dp[i] <= dp[j]:
					dp[i] = 1 + dp[j]
		return max(dp)

	def checkPossible(self, s1, s2):
		if len(s1) + 1 != len(s2):
			return False
		(i, j) = (0, 0)
		flag = 0
		while i < len(s1) and j < len(s2):
			if s1[i] != s2[j]:
				if flag == 1:
					return False
				flag += 1
				j += 1
			else:
				i += 1
				j += 1
		return True


class Solution:

	def isPred(self, a, b):
		if len(a) + 1 != len(b):
			return False
		flag = 0
		i = 0
		j = 0
		while i < len(a) and j < len(b):
			if a[i] != b[j]:
				if flag == 1:
					return False
				flag += 1
				j += 1
			else:
				i += 1
				j += 1
		return True

	def longestChain(self, N, words):
		words = sorted(words, key=lambda x: len(x))
		dp = [1 for i in range(N)]
		for i in range(N):
			for j in range(i):
				if self.isPred(words[j], words[i]) and dp[i] <= dp[j]:
					dp[i] = dp[j] + 1
		return max(dp)


def cmps(s1, s2):
	if len(s1) != len(s2) + 1:
		return False
	f = 0
	s = 0
	while f < len(s1):
		if s < len(s2) and s1[f] == s2[s]:
			f += 1
			s += 1
		else:
			f += 1
	if s == len(s2) and len(s1) == f:
		return True
	return False

class Solution:

	def longestChain(self, N, words):
		dp = [1 for i in range(N)]
		words.sort(key=len)
		for i in range(N):
			for j in range(i):
				if cmps(words[i], words[j]) and dp[j] + 1 > dp[i]:
					dp[i] = dp[j] + 1
		return max(dp)


class Solution:

	def longestChain(self, N, words):
		dp = {}
		words.sort(key=lambda x: len(x))
		for i in words:
			dp[i] = 1
			for j in range(len(i)):
				prev = i[:j] + i[j + 1:]
				if prev in dp:
					dp[i] = max(dp[i], dp[prev] + 1)
		return max(dp.values())