class Solution {
public:
    bool isIsomorphic(string s, string t) {
        vector <int> sfreq (26,0);
        vector <int> tfreq (26,0);
        for (int i=0; i<s.size(); i  ) {
            sfreq[s[i]-'a']  ;
            tfreq[t[i]-'a']  ; 
        }
        
        if (sfreq != tfreq) {
            return false;
        }
        return true;
        }
        
        };

Hi, this is my code in c , I saw something similar from https://www.geeksforgeeks.org/check-if-two-given-strings-are-isomorphic-to-each-other/ but my answer shows it's wrong. Can anyone please tell me why it's wrong?

CodePudding user response：

You completely misunderstood the description.

Your question suggests that any permutation of characters in input do not change answer. Also you assumed that histograms are equal.

Position of character is important. Each position in both strings creates a unique pair.

Here my code which passed:

class Solution {
public:
    static bool canMapInOneDirection(std::string_view s, std::string_view t)
    {
        const auto n = s.size();
        std::array<char, 128> mapping{};
        for(size_t i = 0; i < n;   i) {
            if (mapping[s[i]] == 0) mapping[s[i]] = t[i];
            else if (mapping[s[i]] != t[i]) return false;
        }
        return true;   
        
    }
    bool isIsomorphic(string s, string t)
    {
        return s.size() == t.size() && canMapInOneDirection(s, t) && canMapInOneDirection(t, s);
    }
};

And test cases you can use to test your code:

https://godbolt.org/z/61EcTK5fq

CodePudding user response：

This not a question about anagrams or directly about character frequencies. It is about pattern. It's about having a character-by-character mapping that makes one string into the other. AABC is isomorphic to XXYZ but not isomorphic to BCAA.

When we talk about Isomorphism (same form) it's often a good idea to look for a signature representation. So instead of determining if two strings are isomorphic I've decided to define a unique signature representation and determine isomorphism if two strings map to the same signature.

I've used std::vector<char> for the signature representation such that the first character (if any) is assigned 0 the second (previously unseen) character 1 and so on.

So a string like MOON has signature {0,1,1,2} because the middle characters are the only repeats. MOON is isomorphic to BOOK but not NOON.

The advantage of such a strategy is that if many strings are to be compared to find groups of mutually isomorphic strings each string need only be converted to its signature once.

#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>


std::vector<char> get_signature(const std::string& str){
    std::vector<char> result;
    std::unordered_map<char,char> map;
    char curr{1};
     
  for(auto cchar : str){
    char& c{map[cchar]};
    if(c==0){
        c=curr  ;
     }
     result.emplace_back(c-1);
   }
    return result;
}


int check_signature(const std::string& str, const std::vector<char>& expect ){
    const auto result{get_signature(str)};
    return result==expect?0:1;
}


int main() {
     int errors{0};
     {
        const std::string str{"ABCDE"};
        const std::vector<char> signat{0,1,2,3,4};
        errors =check_signature(str,signat);
     }
     {
        const std::string str{"BABY"};
        const std::vector<char> signat{0,1,0,2};
        errors =check_signature(str,signat);
     }
     {
        const std::string str{"XXYZX"};
        const std::vector<char> signat{0,0,1,2,0};
        errors =check_signature(str,signat);
     }
     {
        const std::string str{"AABCA"};
        const std::vector<char> signat{0,0,1,2,0};
        errors =check_signature(str,signat);
     }
     {
        const std::string str{""};
        const std::vector<char> signat{};
        errors =check_signature(str,signat);
     }
     {
        const std::string str{"Z"};
        const std::vector<char> signat{0};
        errors =check_signature(str,signat);
     }
     if(get_signature("XXYZX")!=get_signature("AABCA")){
          errors;
     }
     
      if(get_signature("MOON")==get_signature("AABCA")){
          errors;
     }
     if(get_signature("MOON")!=get_signature("BOOK")){
          errors;
     }
     if(get_signature("MOON")==get_signature("NOON")){
          errors;
     }

     if(errors!=0){
        std::cout << "ERRORS\n";
     }else{
        std::cout << "SUCCESS\n";
     }
    return 0;
}

Expected Output: SUCCESS

CodePudding user response：

Because you are missing a loop.

Note that, it still requires more corner case checking to make it fully work. The second approach properly handles all cases.

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        vector <int> sfreq (26,0);
        vector <int> tfreq (26,0);

        for (int i=0; i < s.size(); i  ) {
            sfreq[s[i]-'a']  ;
            tfreq[t[i]-'a']  ; 
        }
        
        // character at the same index (can be different character) should have the same count.
        for(int i= 0; i < s.size(); i  )
            if (sfreq[s[i]-'a'] != tfreq[t[i]-'a']) return false;

        return true;
    }
};

But the above solution only works if there is direct index mappping between characters. Like, AAABBCA and XXXYYZX. But fails for bbbaaaba and aaabbbba. Also, no uppercase, lowercase handled. The link you shared contains the wrong implementation which is mentioned in the comment.

The solution below works as I tested.

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        vector<int> scount(128, -1), tcount(128, -1);
        for (int i = 0; i < s.size();   i) {
            auto schar = s[i], tchar = t[i];
            if (scount[schar] == -1) {
                scount[schar] = tchar;
                if (tcount[tchar] != -1) return false;
                else tcount[tchar] = schar;
            } else if (scount[schar] != tchar) return false;
        }
        return true;
    }
};