Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Reddit
Contact us
Hide Buttons

Determine given a pattern and string are isomorphic

Problem :

Given a pattern and a string str, find if str follows the same pattern.
Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Examples:

pattern = "abba", str = "dog cat cat dog" should return true.
pattern = "abba", str = "dog cat cat fish" should return false.
pattern = "aaaa", str = "dog cat cat dog" should return false.
pattern = "abba", str = "dog dog dog dog" should return false.

Notes:
You may assume pattern contains only lowercase letters, and str contains lowercase letters separated by a single space.

Logic :

  • Convert string 2 which contains multiple words into an array of strings
  • Check length of both the string1 with the length of array2
    • If they are of not equal length then return false
  • Create a character map use characters from string 1 as key and map it with array 2
  • While iterating over the string if string 1’s character does not exist in the hash map then add it to the hash map and map it to the array 2’s value
  • If it exists then compare it with the array 2’s character

Solution :

You may also like...

1 Response

  1. ujjaini mukherjee says:

    This can also be done using Map function of Array
    function isomorphic(pat,str){
    var strArr = str.split(‘ ‘);
    if (pattern.length !== strArr.length){
    return false;
    }else{
    var mymap = new Map();
    for(var i=0;i<pat.length;i++){
    if (mymap.has(pat[i])){
    var elm = mymap.get(pat[i]);
    if (elm !== strArr[i]){
    return false;
    }
    }else{
    mymap.set(pat[i], strArr[i]);
    }

    }
    return true;
    }

    }

    var pattern = 'abba', test1 = 'dog cat cat dog', test2 = 'dog cat fly dog';
    console.log(isomorphic(pattern,test1)); // true
    console.log(isomorphic(pattern,test2)); // false

Leave a Reply

Your email address will not be published. Required fields are marked *