You are given two strings A and B of the same length.
Write a script to return true if string B is a scramble of string A otherwise return false.
String B is a scramble of string A if A can be transformed into B by a single (recursive) scramble operation.
A scramble operation is:
- If the string consists of only one character, return the string.
- Divide the string X into two non-empty parts.
- Optionally, exchange the order of those parts.
- Optionally, scramble each of those parts.
- Concatenate the scrambled parts to return a single string.
It is tempting to just create all possible scrambles of an input value, and see whether one of them matches the target. But this quickly becomes unfeasible with strings containing more than a dozen of so characters. A string of 12 (different) characters has 39,916,800 permutation, of which 1,037,718 are valid scrambles (and many scrambles have more than one path leading to it).
Instead, we will use the following steps to determine whether we can scramble one string into another:
We start off with a helper function are_anagrams. It takes two string,
and returns true iff the strings are anagrams of each other. To determine
that, we split each string into single character strings, sort them, then
rejoin them. The two strings are anagrams iff the resulting strings
(after the join) are equal:
sub are_anagrams ($str1, $str2) {
join ("" => sort split // => $str1) eq
join ("" => sort split // => $str2)
}
It's now easy to write a can_scramble subroutine following the
steps outlined above:
sub can_scramble ($input, $target) {
return 1 if $input eq $target; # Equal?
return 0 if length ($input) != length ($target); # Same length?
return 0 unless are_anagrams ($input, $target); # Anagrams?
#
# Recurse
#
for (my ($l, $m) = (1, length ($input) - 1); $m >= 1; $l ++, $m --) {
return 1 if
can_scramble (substr ($input, 0, $l), substr ($target, 0, $l)) &&
can_scramble (substr ($input, $l, $m), substr ($target, $l, $m)) ||
can_scramble (substr ($input, $l, $m), substr ($target, 0, $m)) &&
can_scramble (substr ($input, 0, $l), substr ($target, $m, $l));
}
return 0; # No solution found
}
Find the full program on GitHub.
We use the same algorithm in Go as we used in Perl, but Go makes us work harder. Go does have strings as a type, but strings are arrays (or slices) of bytes. We want to work with characters, called runes in Go. So we need to do some conversions.
First, the are_anagrams function:
func are_anagrams (str1 string, str2 string) bool {
a_str1 := [] rune (str1)
a_str2 := [] rune (str2)
What we did here was turning the strings into slices of runes.
We can then sort the arrays — we have to pass in a sort method, and the sorting is done in situ:
slices . SortFunc (a_str1, func (a, b rune) int {
if a < b {return -1}
if a > b {return 1}
return 0
})
The string function turns a slice of runes back into a string, and
we can compare the strings:
return string (a_str1) == string (a_str2)
We need an additional helper function. Go has syntax to take slices out
of strings, but they operate on bytes, not runes. So make a helper
function substr which turns the string into arrays of runes, takes
slices of those arrays, then turn them back into strings:
func substr (str string, start int, end int) string {
runes := [] rune (str)
if start < 0 {start += len (runes) + 1}
if end < 0 {end += len (runes) + 1}
return string (runes [start : end])
}
The can_scramble function is then straight forward. Note the method
utf8 . RuneCountInString which gives the number of runes in a string.
func can_scramble (input string, target string) bool {
if input == target {return true} // Equal?
if utf8 . RuneCountInString (input) != utf8 . RuneCountInString (target) {
return false // Same length?
}
if !are_anagrams (input, target) {return false} // Anagrams?
// Recurse
for l := 1; l < utf8 . RuneCountInString (input); l ++ {
m := utf8 . RuneCountInString (input) - l
if can_scramble (substr (input, 0, l), substr (target, 0, l)) &&
can_scramble (substr (input, l, -1), substr (target, l, -1)) ||
can_scramble (substr (input, l, -1), substr (target, 0, m)) &&
can_scramble (substr (input, 0, l), substr (target, m, -1)) {
return true
}
}
return false
}
Find the full program on GitHub.
We also have solutions in AWK, C, Lua, Node.js, Python, Ruby, and Tcl.