need solution to be in Python 2 String Chains Given an array, words, of n word s
ID: 2247179 • Letter: N
Question
need solution to be in Python 2
String Chains Given an array, words, of n word strings (words[O), words[11, , words n-1), choose a word from it and, in each step, remove a single letter from the chosen word if and only if doing so yields another word that is already in the library. Each successive character removal should be performed on the result of the previous removal, and you cannot remove a character if the resulting string is not an element in words (see the Explanation below for detail). The length of a string chain is the maximum number of strings in a chain of successive character removals Complete the longestChain function in your editor. It has 1 parameter: an array of n strings, words, where the value of each element wordsi (where 0 siExplanation / Answer
def Findlonges(set1, dict1, x):
if x not in dict1:
ret = 1
for i in xrange(len(x)):
w = x[:i] + x[i+1:]
if w and w in set1:
cnt = Findlonges(set1, dict1, w)
ret = max(ret, 1 + cnt)
dict1[x] = ret
return dict1[x]
def findStringChain(list1):
dict1 = {}
set1 = set(list1)
max1 = 0
for x in list1:
max1 = max(max1, Findlonges(set1, dict1, x))
return max1
def main():
n=input("enter the value of N: ")
m=0
list1=[]
for i in range(0,n):
x=raw_input("enter string: ")
list1.append(str(x))
print findStringChain(list1)
if __name__ == "__main__":
main()
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.