Saturday, July 11, 2015

How to find if you strings are isomorphic
Given two strings s and t, determine if they are isomorphic.
Two strings are isomorphic if the characters in s can be replaced to get t.
All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.
For example,
Given "egg""add", return true.
Given "foo""bar", return false.
Given "paper""title", return true.
Note:
You may assume both s and t have the same length.

Solution
bool IsIsomorphic(string s, string t)
{
map<char, int> smap;
map<char, int> tmap;
bool check = true;
if (s.length() != t.length())
{
        return false;
}

int len = s.length();
int index = 0;

while (index < len)
{
        char sch = s.at(index);
        char tch = t.at(index);
        int finds = smap.find(sch)->second;
        int findt = tmap.find(tch)->second;

        if ((finds > index) && (findt > index))
      {
       // ignore
      }

     if ((finds > index) && (findt < index))
    {
             check = false;
             break;
    }

      if ((finds < index) && (findt > index))
      {
           check = false;
            break;
       }

      if ((finds < index) && (findt < index) && (finds != findt))
       {
              check = false;
              break;
      }

       if (!(smap.count(sch) == tmap.count(tch)))
      {
            check = false;
            break;
       }

      smap[sch] = index;
      tmap[tch] = index;
      index++;
    }

return check;
}

No comments:

Post a Comment