Magic words can be described as below.
Given a list of words L, a word is considered magical, if it can be reduced to a starting root alphabet, recursively, by stripping off one character at a time, and the newly formed word is also present in the list L.
Lets assume the root alphabet is 'A'. So 'A' should be present in the list.
[A]
Now with one word added anywhere, we can have the following magic words.
A[A..Z]
[A..Z]A
Lets pick 2 magic words for our list and extend it.
[A, AN, SA]
To our list we will add a non-magic word.
[A, AN, SA, BC]
Lets extend with some more magic words to clarify the problem.
AN -> ANT
AN -> BAN
SA -> RSA
SA -> SAS
SA -> SPA
BC (non-magic) -> ABC
So new lists looks like
[A, AN, SA, BC, ANT, BAN, RSA, SAS, SPA, ABC]
The point to note here is ABC is not a magic word, as all the sub words ( AB, AC, BC ) are non existent in the list, hence there is no way to recursively reach 'A' by reducing 'ABC' using words present in the list.
Problem :
Given a list of words, find the longest magic word. Assume the root alphabet is always present.
Solution :
Considerations :
As we are trying to find the longest word, we can start off by arranging all the words by decreasing length and check from the longest word if it is magical or not.
Python Code.
wordList = ["a","an","san","sans","saxds","man","said","salds","aid","axds"]
def modifyWord(elem):
list_of_chars = list(elem)
if len(list_of_chars) == 1:
return 1
for index in range(len(list_of_chars)):
newWordList = list_of_chars[:index] + list_of_chars[index+1:] #check for bounds
newWord = "".join(newWordList)
#print newWord
if newWord in wordList:
retVal = modifyWord(newWord)
if retVal:
return 1 + retVal
else:
return 0
return 0
if __name__ == '__main__':
len_sorted_wordList = sorted(wordList, key=len, reverse=True)
for elem in len_sorted_wordList:
print "Elem = ", elem
maxlen = max(0, modifyWord(elem))
if maxlen:
print maxlen
break
In the above code, lets understand the function modifyWord.
The modifyWord takes as an input a word element, and converts it into a list of characters first. If the length is 1, it simply returns the length. So if we pass a root alphabet, we get a return value of '1'.
Otherwise, the code removes a character one at a time and forms the newWord. Now we check if the newWord is in the original list. If present , we call modifyWord on it again, else, we try the same on the next newWord, formed by removing the next index element. The commented print statement is there to show what the newWord looks like.
If you have better solutions please comment, I would love to know. Also other modifications can be, to create a sorted tree from the list using the root alphabet as the root element, to find magic words from a start word rather than a root alphabet, etc.
Given a list of words L, a word is considered magical, if it can be reduced to a starting root alphabet, recursively, by stripping off one character at a time, and the newly formed word is also present in the list L.
Lets assume the root alphabet is 'A'. So 'A' should be present in the list.
[A]
Now with one word added anywhere, we can have the following magic words.
A[A..Z]
[A..Z]A
Lets pick 2 magic words for our list and extend it.
[A, AN, SA]
To our list we will add a non-magic word.
[A, AN, SA, BC]
Lets extend with some more magic words to clarify the problem.
AN -> ANT
AN -> BAN
SA -> RSA
SA -> SAS
SA -> SPA
BC (non-magic) -> ABC
So new lists looks like
[A, AN, SA, BC, ANT, BAN, RSA, SAS, SPA, ABC]
The point to note here is ABC is not a magic word, as all the sub words ( AB, AC, BC ) are non existent in the list, hence there is no way to recursively reach 'A' by reducing 'ABC' using words present in the list.
Problem :
Given a list of words, find the longest magic word. Assume the root alphabet is always present.
Solution :
Considerations :
As we are trying to find the longest word, we can start off by arranging all the words by decreasing length and check from the longest word if it is magical or not.
Python Code.
wordList = ["a","an","san","sans","saxds","man","said","salds","aid","axds"]
def modifyWord(elem):
list_of_chars = list(elem)
if len(list_of_chars) == 1:
return 1
for index in range(len(list_of_chars)):
newWordList = list_of_chars[:index] + list_of_chars[index+1:] #check for bounds
newWord = "".join(newWordList)
#print newWord
if newWord in wordList:
retVal = modifyWord(newWord)
if retVal:
return 1 + retVal
else:
return 0
return 0
if __name__ == '__main__':
len_sorted_wordList = sorted(wordList, key=len, reverse=True)
for elem in len_sorted_wordList:
print "Elem = ", elem
maxlen = max(0, modifyWord(elem))
if maxlen:
print maxlen
break
In the above code, lets understand the function modifyWord.
The modifyWord takes as an input a word element, and converts it into a list of characters first. If the length is 1, it simply returns the length. So if we pass a root alphabet, we get a return value of '1'.
Otherwise, the code removes a character one at a time and forms the newWord. Now we check if the newWord is in the original list. If present , we call modifyWord on it again, else, we try the same on the next newWord, formed by removing the next index element. The commented print statement is there to show what the newWord looks like.
If you have better solutions please comment, I would love to know. Also other modifications can be, to create a sorted tree from the list using the root alphabet as the root element, to find magic words from a start word rather than a root alphabet, etc.
