Today's fun with string manipulation, given two strings, test to see if the first can be shifted to match the second. Some example strings:
"atsc", "cats" ==> yes
"llygaglo", "lollygag" ==> yes
"cacacaca", "acacacac", ==> yes
"elparall", "elparallx", ==> no
The trick here is to consider that letters can occur multiple times and to consider how to address the "wrapping" of the word.
My first cut at this, using Ruby, was a pretty ugly combination of small methods, and frankly really way too long. See here if bothered. https://gist.github.com/bsbonus/1958684d52ebe1434233
Obviously, I wasn't very happy with the attempt. It's long and does a lot of transformation work that seemed unnecessary. So let's try recursion!
Here's the cleaner, recursive version:def reorder_string string1, string2
def reorder_string(string1, string2) if string1 == string2 puts true elsif string1.length != string2.length puts false else check_substrings(string1, string2) end end def check_substrings(string1, string2) if string1.length == 0 puts false else if string2.include?(string1) end_pos = string2.index string1 puts "#{string2[0...end_pos]}#{string1}" else string1 = string1[0..-2] check_substrings(string1, string2) end end end
Technically I could remove the first two if/elseif parts of reorder_string and move them into the check_substrings method, but I think it's faster to immediately remove the easy cases before entering the recursive steps.
The better question to ask is to determine the tradeoffs between the two. The first attempt finds the starting letter of the second word and finds any locations of it in the first word.
E.g. "ygagloll" and "lollygag" => 'l' exists at 4, 6,7 in 'ygagloll'
It then loops over those occurrences, testing at each occurence by transforming the first word at that index so that the word *should* be spelled to match the second word, if the two words match.
Here's my freshman level algorithmic breakdown.
It's On to get all the occurrences and then On to check each letter in turn. But in a worst case scenario, all but the last letter of the first word will match the first letter of the second, eg. "aaaaaaaad" and "aaaaaaaac." Which means ~On occurrences * On checks = On^2 complexity.
So in total: On + On^2, so On^2. Gross.
Alternatively, the recursive strategy starts with the largest possible substring match (n-1) in n (e.g. cat in cats). To find a matching string (if it exists) will take On in worst case.
Recursion FTW.