Skip to content

Instantly share code, notes, and snippets.

@matt-land
Created June 14, 2019 13:21
Show Gist options
  • Save matt-land/fa166e824a1a4aecee0cf839ad5e9e80 to your computer and use it in GitHub Desktop.
Save matt-land/fa166e824a1a4aecee0cf839ad5e9e80 to your computer and use it in GitHub Desktop.
LongestStringChain implementation in python
word_list = ['a',
'b',
'ba',
'bca',
'bda',
'bdca'
]
short = ['a', 'c', 'e']
apple = ['sapple', 'apple', 'a']
def longestStringChain(word_list):
max = 0
for word in word_list:
depth = find_subword_count(word, word_list)
if depth > max:
max = depth
return max + 1
def find_subword_count(current_word, word_list):
if len(current_word) == 1:
return 0
max = 0
for i in range(len(current_word)):
chars = list(current_word)
del chars[i]
subword = ''.join(chars)
if subword not in word_list:
continue
count = 1 + find_subword_count(subword, word_list)
if max >= count:
continue
max = count
return max
print(longestStringChain(word_list))
print(longestStringChain(short))
print(longestStringChain(apple))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment