Welcome back to week five of the weekly programming contests! As always, you can find the rules and information on the contests Posted Here
This weeks challenge is slightly similar to the anagram challenge in week two. Your job is to test whether or not two Strings are Isomorphic. For this challenge, Isomorphic Strings will be any two Strings in which it is possible to replace the characters in either one in order to get the other.
For example, “egg” and “add” would be isomorphic because e -> a and g -> d and the inverse works as well. However “coot” and “toot” would not be, because c -> t and t -> t which means that t maps to both t and c going the other way making isomorphicality impossible.
You have to implement this functionality in the method: public static boolean isomorphic(String a, String b) (The method can be renamed), which returns true if the Strings are isomorpic and false if they are not, case insensitive.
Minified version: 147 chars (138 with method renamed to i)
public static boolean isomorphic(String a,String b){return Arrays.equals(a.chars().map(a::indexOf).toArray(),b.chars().map(b::indexOf).toArray());}
How it works:
A String is isomorphic to cool, if it contains four characters, of which all are different from each other except for the second and third character, which are the same.
Or, more verbose: The first character first occurs on positon 1. The second character first occurs on position 2. The third character first occurs on position 2. The fourth character first occurs on position 4.
So for each String I create a description in form of an int array (which for “cool” is {0,1,1,2}) by mapping each character to the position where it first occurs. Two Strings then are isomorphic if and only if their descriptions are equal.
Edit: Shaved off a total of 20 chars of the initial solution: 10 by removing fully qualified name as imports do not count towards code length and another 10 by using method references instead of lambda expressions.
I’d prefer scala for this, or if you use the Functional Java library, foldLeft would reduce this code by even more. But sticking to pure jdk, here’s an improvement on your take of this challenge.
This simplification works by the same logic @Saladoc used. Comparing the resulting mapped array via the first index of the char. Since they should be the same, the sums should also be the same. It passes the test that @Saladoc used for his function, and there might be an edge case, but to high to think of any. This works just fine for the contest.
Minified: (125 chars)
public static boolean isomorphic(String a,String b){return a.chars().map(a::indexOf).sum()==b.chars().map(b::indexOf).sum();}
Non-minified:
public static boolean isomorphic(String a, String b) {
return a.chars().map(a::indexOf).sum() == b.chars().map(b::indexOf).sum();
}
Credits: Saladoc for actual logic and initial code. This is just an improvement to help those who don’t understand the power of functional style programming.
Note: This is smaller than @Saladoc’s answer, however, credit him with the winning solution if no one else can produce something shorter, because credit is due where its due.
Nice improvement. It will work for all the examples given by @kmecpp and will return true for every pair of isomorphic strings.
Sadly, there will be tons of false positives. For example, the strings “aaabb” and “aabbb” are obviously not isomorphic and will be described as {0,0,0,3,3} and {0,0,2,2,2} respectively. However, both of these descriptions have the same sum and therefore will be falsely recognised as isomorphic by your approach.