Checking whether two strings are isomorphic

Question

I was trying to solve a problem to determine if 2 strings are isomorphic. They are isomorphic when each character in string one can be replaced with another character in string 2. Two different characters may not map to the same value, and same character must not match to different values. Also the length of the strings must be same.

I've used exception for logic flow:

module Isomorphism
 class NotIsomorphicException < StandardError
 attr_reader :object
 def initialize(object)
 @object = object
 end
 end
 def self.isomorphic? string_a,string_b
 begin
 self.isomorphism string_a,string_b
 true
 rescue NotIsomorphicException => _
 return false
 end
 end
 protected
 def self.isomorphism string_a,string_b
 raise NotIsomorphicException.new("Unequal length") unless string_a.size == string_b.size
 isomorphism_map = {}
 associations = string_a.chars.zip string_b.chars
 associations.each do |char_one,char_two|
 if(isomorphism_map.key? char_one)
 raise NotIsomorphicException.new("Single character needs to map to multiple characters, not isomorphic") unless isomorphism_map[char_one] == char_two
 elsif(isomorphism_map.value? char_two)
 raise NotIsomorphicException.new("Two characters map to same value")
 end
 isomorphism_map[char_one] = char_two
 end
 end
end

Please let me know if it's okay to code this way and any improvements that I might be able to make this better.

Following are the specs, just in case:

describe Isomorphism do
 it "should return true for single character words" do
 expect(Isomorphism.isomorphic? "t","d").to be true
 end
 it "should return true for empty strings" do
 expect(Isomorphism.isomorphic? "","").to be true
 end
 it "should return false if strings are of unequal length" do
 expect(Isomorphism.isomorphic? "dh","dhruv").to be false
 end
 it "should return false when 2 characters need to map to same character" do
 expect(Isomorphism.isomorphic? "ab","aa").to be false
 end
 it "should return true for egg and add" do
 expect(Isomorphism.isomorphic? "egg","add").to be true
 end
 it "should return false for foo and bar" do
 expect(Isomorphism.isomorphic? "foo","bar").to be false
 end
 it "should return true for paper and title" do
 expect(Isomorphism.isomorphic? "paper","title").to be true
 end
 it "should return false for aab and aaa" do
 expect(Isomorphism.isomorphic? "aab","aaa").to be false
 end
end

Answer 1

Looking at your isomorphism helper function...

The flow of control is kind of nasty. In particular, burying an unless in here...

if ...
 raise Exception.new(...) unless ...
elsif ...
 raise
end

... is too tricky, because:

• You already have an if-elsif expression, and it would be better to work it into the same chain.
• It's at the end of a very long line, where it is barely visible.
• unless, being a negation, is automatically less preferable to an affirmative if.

Switching the naming convention from string_a, string_b to char_one, char_two is not ideal. Why not char_a, char_b? Or better yet, just a, b?

Doing Hash lookups in reverse using value? is not efficient. You would be better off making a "forward" map and an "inverse" map. See below for an even better way to decompose the problem.

As for the use of exceptions internally, I think it's a bad idea. It's just a cumbersome way to return false with commentary. You could just write a comment to avoid the overhead. Better yet, if you write the code well, I don't think there is a need for any comment. For example, in the implementation below, b != expected_b is pretty self-explanatory.

module Isomorphism
 def self.isomorphic?(string_a, string_b)
 surjective?(string_a, string_b) && surjective?(string_b, string_a)
 end
 protected
 def self.surjective?(string_a, string_b)
 return false if string_a.size != string_b.size
 surjection = {}
 string_a.chars.zip(string_b.chars).each do |a, b|
 expected_b = surjection[a]
 if expected_b && (b != expected_b)
 return false
 end
 surjection[a] = b
 end
 true
 end
 # Alternate implementation: shorter, but won't detect failure as quickly
 def self.surjective?(string_a, string_b)
 return false if string_a.size != string_b.size
 pairs = string_a.chars.zip(string_b.chars)
 surjection = Hash[pairs]
 pairs.all? { |a, b| surjection[a] == b }
 end
end

• Dhruv Kapur: I used most of what I did to prevent returning true/false from a function that's can return isomorphic strings (currently its not doing that, but it can) Secondly for me, the symbol ! for not is very short and often skips my eyes, but I guess that's just me. I like how you captured rules in 2 calls to surjective. And yep I messed up naming conventions, but is a,b better than char_a,char_b? a,b doesn't tell me that these are chars... or is it okay to expect that from the context. Thanks for the suggestions though, your code if ofcourse much simplified :)
• 200_success: Related answer in Java

Answer 2

Well, 200_success beat me to it, but I'd already written this. I'm stealing the name surjective?, though.

I don't see the need for exceptions. Just return.

Sure, exceptions can tell more about why two strings aren't isomorphic, but you're not using that for anything - not even inside your module. And the exceptions don't bubble back to the caller, so it seems like you go to a lot of trouble to raise exceptions and then immediately rescue from them.

By the way, you could consider mixing this into the String class. Not saying you have to, but you could.

class String
 def isomorphic?(string)
 surjective?(string) && string.surjective?(self)
 end
 def surjective?(string)
 return false unless length == string.length
 chars.zip(string.chars).each_with_object({}) do |(a, b), map|
 return false if map[a] && map[a] != b
 map[a] = b
 end
 true
 end
end

• Dhruv Kapur: Okay - if this is prod code will you put comments on why are we returning false? And thanks for each_with_object - didn't know about that function :)
• Dhruv Kapur: And I'll upvote you for good use of open classes and unless once I've enough repo on the site
• Flambino: @DhruvKapur In production I'd probably document the methods overall, but I wouldn't bother with comments inside the method bodies. I'd write something like what you wrote in your question (i.e. this is what does isomorphic mean for strings). However, in production I tend to be very conservative about extending core classes like String. It's neat, but I won't go there unless it's really, really worth it. I did it in my answer just to present the idea.

Answer 3

I do not match Code Review with this a lot, but I found this problem to be interesting and would solve it without .zip and {}:

def isomorphic? a, b
 each_char_positions = lambda do |string|
 string.each_char.map.with_index.group_by(&:first).
 map{ |c, poss| poss.map(&:last) }.sort
 end
 each_char_positions[a] == each_char_positions[b]
end

Strings are isomorphic if arrays of their unique chars positions are the same. You may insert tap{ |s| p s }. line after group_by to see this for "paper" vs "title":

{"p"=>[["p", 0], ["p", 2]], "a"=>[["a", 1]], "e"=>[["e", 3]], "r"=>[["r", 4]]} 
{"t"=>[["t", 0], ["t", 2]], "i"=>[["i", 1]], "l"=>[["l", 3]], "e"=>[["e", 4]]}