thzinc

isIsomorphic - Interview question of the week from rendezvous with cassidoo

Wow, I haven’t done one of these for a few months. Let’s see how this goes!

Interview question of the week

This week’s question: Given two strings s and t, determine if they are isomorphic. Two strings are isomorphic if there is a one-to-one mapping possible for every character of the first string to every character of the second string.

Example:

> isIsomorphic('abb', 'cdd')
> true // 'a' maps to 'c' and 'b' maps to 'd'

> isIsomorphic('cassidy', '1234567')
> false // 's' cannot have a mapping to both '3' and '4'

> isIsomorphic('cass', '1233')
> true

My solution

Off the top of my head, I think this can be solved in roughly O(n) if I keep a mapping of observed characters along the way. I should be able to exit early if I encounter a new mapping that doesn’t match a previously-observed mapping.

#mocha

  

function isIsomorphic(a, b) {
  const count = a.length;
  if (count != b.length) return false;

  const mappings = {};
  for (let i = 0; i < count; i++) {
    const currA = a[i];
    const currB = b[i];

    const mapping = mappings[currA];
    if (!mapping) {
      mappings[currA] = currB;
    } else if (mapping !== currB) {
      return false;
    }
  }
  return true;
}


mocha.setup("bdd");
const assert = chai.assert;
const expect = chai.expect;
const should = chai.should();

describe("Given valid inputs", () => {
  it("should succeed with a trivial example", () => {
    isIsomorphic("abb", "cdd").should.be.true;
  });
  it("should fail with a trivial example", () => {
    isIsomorphic("cassidy", "1234567").should.be.false;
  });
  it("should succeed with another trivial example", () => {
    isIsomorphic("cass", "1233").should.be.true;
  });
});
describe("Extra assertions", () => {
  it("should fail with strings of different lengths", () => {
    isIsomorphic("short", "very long").should.be.false;
    isIsomorphic("very long", "short").should.be.false;
  });
});

mocha.run();








      

      
      

        
See also