Rearrange Strings Solution in JavaScript
I came across a challenge to programmatically determine if, given a set of strings, there was a combination of strings where each string was different from the next one by a single character. So I decided to take it on.
This article will go through two main things:
- A methodology of solving this type of problem
- A walk-through of the solution code using JavaScript
Here's an example:
Let's say we have the following array of strings:
["aba", "bbb", "bab"] // No combination exists
If we try to reorder this set of strings, we won't find any combination of them where each consecutive string differs by one character. Now let's look at this set of strings:
["bb","aa","ab"] // Can be rearranged to bb,ab,aa
We can see that it is possible to rearrange this set of strings so that each consecutive string differs by one character.
So, how would you go about solving this?
There is a mathematical concept in graph theory called a Hamiltonian Path. I won't get into the math and logic behind it here, but I will briefly discuss some of the high-level pseudo-code to understand how to approach the problem (check out the sources at the end of the article for more technical details on Hamiltonian Paths!).
First, think of a Hamiltonian Path like this: a delivery man has a map of New York City and marks all the points he has to visit to drop off a package. He has to visit 10 houses. Now, because gas prices are so high and he wants to minimize how much has to drive thus saving him money, he wants to visit each house only once without having to drive by a house he already delivered a package to. So, he needs to find a route that takes him to each of the 10 houses without driving by one he already visited. This money-saving route would be considered a Hamiltonian Path.
Here's a visual representation of this concept:
From our string examples above, each string in the array is like a point on the delivery man's map. If a string differs from its neighbor string by one character, that represents a valid connection to those two points on the map. If a string differs by multiple characters, that represents that point having multiple connections and the delivery man would have to visit that point more than once. This cycle occurs recursively for each connecting point in a path until a valid path connecting all points from start to finish is found. (Related note: a Hamiltonian Path is considered NP-complete because it determines THAT a solution exists, not necessarily the BEST solution, because that would require to know all the possible solutions first, which dramatically increases the amount of time to find a solution. Case in point, another valid path from the image above is 0,1,3,2, but only the first match 0,1,2,3 will return true.)
Whew! You're still here! Great, let's keep going...
Pseudo-code Explained
We will need to implement the concept of finding a Hamiltonian Path to write a solution for rearranging the strings. Below is a high-level run down of the logic:
Given our input array:
["bb","aa","ab"] // Input array
For each string in the array, we need to do two things:
- Recursively compare for adjacent strings
- Check if those two strings have a valid connection (signified as having only one difference in characters)
We would first grab "bb" and recursively check against the input array for the next valid neighbor, in this case would be "ab". The validation compares each character in the adjacent string. If the count of different characters is exactly 1, then there is a valid connection between those two points. The first comparison in the loop will be "bb" and "aa", which will yield an invalid connection since the strings differ by 2 characters. So that means that "bb" can't be next to "aa", so skip it and move on to the next available string to see if it can connect to "bb". Once the connection between "bb" and "ab" is determined valid, we'll now need to check if there are any valid connections from "ab". So we'll do all the checks against inputArray again and this time will see that "ab" and "aa" have a valid connection. Putting it all together, "bb" and "ab" have a connection and "ab" and "aa" have a connection, so combining all the valid connections together creates "bb", "ab", "aa", which is a valid path!
The Code!
Here is my JavaScript solution to the rearrange strings challenge. I also have associated test cases written in JasmineJS. Click on the image to check it out on GitHub!
If you made it this far, I applaud you! Please give me your thoughts on how this approach could be improved and optimized or other ways you would apply this algorithm in real life. I'd love to hear from you!
Sources and References
Hacker Earth - Hamiltonian Path