WolfDelaymaster
Problem Statement
Wolf Sothe is playing the game Delaymaster. In this game, he can create new words according to the following rules:Thus, for example:You are given aStringstr. Return "VALID" ifstris a valid word and "INVALID" otherwise. Note that the return value is case-sensitive: you must return the strings "VALID" and "INVALID" in all-uppercase.
Definition
ClassWolfDelaymasterMethodcheckParametersstringReturnsstringMethod signaturestring check(string str)
(be sure your method is public)
Limits
Constraintsstrwill contain between 1 and 50 characters, inclusive.Each character instrwill be ‘w’, ‘o’, ‘l’ or ‘f’.
Test cases
str"wolf"
Returns"VALID"
The first valid word from the examples in the problem statement.
str"wwolfolf"
Returns"INVALID"
The second invalid word from the examples in the problem statement.
str"wolfwwoollffwwwooolllfffwwwwoooollllffff"
Returns"VALID"
str"flowolf"
Returns"INVALID"
We can see this one as a standard recursive problem or as a parsing problem.
Recursion
Let us redefine a valid string as a concatenation between a valid string and a string that follows the pattern: ww…woo…oll…lff…f . The most complicated valid example case is:
wolfwwoollffwwwooolllfffwwwwoooollllffff
"wolfwwoollffwwwooolllfff" is a valid string and "wwwwoooollllffff" follows the repeated pattern.
as a function that returns true if and only if the stringsis valid. We know that it must end with a string that follows the repeated pattern. It is easy to generate a string ofcharacters that follows the pattern, whereris positive. (For example, for: wwoollff. For each, we can determine if the string ends with a repeated pattern string. Then we just need to check if the firstcharacters of the string make a valid string. This is the same as calling, whereis the string that is composed of the firstcharacters of the string. If there is a repeated pattern AND the remaining string is also valid then the complete string is also valid.
We need a base case, eventually the string will be a single repeated pattern, which will make the remaining string the empty string. We can consider the empty string valid.
calls at most one other instance ofin whichis strictly smaller. E.g: If the string finishes with ‘wolf’ it cannot finish with ‘wwoollff’. We don’t need memoization to make it run in time and it wouldn’t really be dynamic programming to fill it iteratively.
class WolfDelaymaster: def check(self, s):# function returns w (r times) o (r times) l (r times) f (r times):def wolf(r):return ''.join( ch * r for ch in "wolf" )if s == '':return "VALID"r = 1while 4 * r <= len(s):# s[-4*r:] equals the last 4*r characters in the stringif wolf(r) == s[-4*r:] :return self.check( s[ :-4*r] ) #recurse# s[-4*r:] equals the other charactersr += 1# if we didn't find any repeated pattern, it is invalid:return "INVALID"
String parsing
We can also try to just parse the string following the rules until we find a mistake.
We know that the string must start withw. If that is not the case, then the string is invalid.Count the number of initialws, let it ber. The following lettersmustber’o’ characters, thenr’l’ characters andr’f’ characters.After finding thefcharacters, restart over, the next character must bew, count the number ofwand repeat until we find the end of string until a validfcharacter.
The code is more complicated but it works:
愈想得到，就愈要放手。放手是很难的，但是别无选择。
