# Checking whether two strings are isomorphic

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
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
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


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

• 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 :) – Dhruv Kapur May 1 '15 at 1:30
• Related answer in Java – 200_success May 27 '16 at 8:15

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

• 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 May 1 '15 at 1:34
• And I'll upvote you for good use of open classes and unless once I've enough repo on the site – Dhruv Kapur May 1 '15 at 1:37
• @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. – Flambino May 1 '15 at 2:29

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]]}