ef height(words, word): The length of a word is easy enough to define by tallying up its characters. Taking the road less traveled, we define the height of the given word with a recursive rule for the height of the given word to follow from the heights of two words whose concatenation it is. First, any character string that is not one of the actual words automatically has zero height. Second, an actual word that cannot be broken into a concatenation of two nonempty actual words has the height of one. Otherwise, the height of an actual word equals one plus the larger of the heights of the two actual words whose combined concatenation it can be expressed as. To make these heights unambiguous for words that can be split into two non-empty subwords in multiple ways, this splitting is done the best way that produces the tallest final height. Since the list of words is known to be sorted, you can use binary search (available as the function bisect_left in the bisect module) to quickly determine whether some subword is an actual word. Be mindful of the return value of that function whenever the parameter string is not an actual word, and also the edge case of subwords that start with two or more copies of the letter z. word Expected result 'hxllo' 0 'chukker' 1 'asteroid' 7 'pedicured' 2 'enterprise' 6 'antidisestablishmentarianism' 11 'noncharacteristically' 13 In the wordlist every individual letter seem to be a word of its own, which makes these word heights much larger than we expect them to be. Narrowing the dictionary to cover only everyday words would make most of these word heights topple. Finally, words such as 'mankind' steadfastly thumb their noses at humanity by splitting only into nonsense such as 'mank' and 'ind'. The meaning of those words is a mystery, and that’s why so is mankind...
def height(words, word):
The length of a word is easy enough to define by tallying up its characters. Taking the road less traveled, we define the height of the given word with a recursive rule for the height of the given word to follow from the heights of two words whose concatenation it is.
First, any character string that is not one of the actual words automatically has zero height. Second, an actual word that cannot be broken into a concatenation of two nonempty actual words has the height of one. Otherwise, the height of an actual word equals one plus the larger of the heights of the two actual words whose combined concatenation it can be expressed as. To make these heights unambiguous for words that can be split into two non-empty subwords in multiple ways, this splitting is done the best way that produces the tallest final height.
Since the list of words is known to be sorted, you can use binary search (available as the function bisect_left in the bisect module) to quickly determine whether some subword is an actual word. Be mindful of the return value of that function whenever the parameter string is not an actual word, and also the edge case of subwords that start with two or more copies of the letter z.
|
word |
Expected result |
|
'hxllo' |
0 |
|
'chukker' |
1 |
|
'asteroid' |
7 |
|
'pedicured' |
2 |
|
'enterprise'
|
6 |
|
'antidisestablishmentarianism'
|
11 |
|
'noncharacteristically'
|
13 |
In the wordlist every individual letter seem to be a word of its own, which makes these word heights much larger than we expect them to be. Narrowing the dictionary to cover only everyday words would make most of these word heights topple. Finally, words such as 'mankind' steadfastly thumb their noses at humanity by splitting only into nonsense such as 'mank' and 'ind'. The meaning of those words is a mystery, and that’s why so is mankind...
Step by step
Solved in 2 steps
