Isomorphic Strings

Question

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.

I have this solution but it is taking too much time. Any good solution will be appreciated

   public boolean isIsomorphic(String s, String t) {
        String resString1="",resString2="";
            HashMap<Character,Integer> hashmapS = new HashMap(); 
            HashMap<Character,Integer> hashmapT = new HashMap(); 
            boolean flag = false;
            for(int i = 0;i<s.length();i++)
            {
              char chS = s.charAt(i);
              char chT = t.charAt(i);
              if(hashmapS.containsKey(chS))
              {
                  resString1 = resString1 + hashmapS.get(chS);
              }
              else
              {
                  resString1 = resString1 + i; 
                  hashmapS.put(chS, i);
              }
              if(hashmapT.containsKey(chT))
              {
                  resString2 = resString2 + hashmapT.get(chT);
              }
              else
              {
                  resString2 = resString2 + i; 
                  hashmapT.put(chT, i);
              }
            }
           if(resString1.equals(resString2))
               return true;
           else
               return false;
    }

Bother

Answer 1

Here is another implementation but with less memory usage.

public class IsoMorphic {
    private static boolean isIsomorphic(String s, String t) {
        if (s.length() != t.length()) {
            return false;
        }
        char characters1[] = new char[26];
        char characters2[] = new char[26];
        char array1[] = s.toCharArray();
        char array2[] = t.toCharArray();

        for (int i=0; i<array1.length; i++) {
            char c1 = array1[i];
            char c2 = array2[i];
            char character1 = characters1[c1-'a'];
            char character2 = characters2[c2-'a'];
            if (character1 == '\0' && character2 == '\0') {
                characters1[c1-'a'] = array2[i];
                characters2[c2-'a'] = array1[i];
                continue;
            }
            if (character1 == array2[i] && character2 == array1[i]) {
                continue;
            }
            return false;
        }
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isIsomorphic("foo", "bar"));         // false
        System.out.println(isIsomorphic("bar", "foo"));         // false
        System.out.println(isIsomorphic("paper", "title"));     // true
        System.out.println(isIsomorphic("title", "paper"));     // true
        System.out.println(isIsomorphic("apple", "orange"));    // false
        System.out.println(isIsomorphic("aa", "ab"));    // false
        System.out.println(isIsomorphic("ab", "aa"));    // false
    }
}

Kolnos

Your implementation does not cover the case when: Input: "ab" "aa" Output: true Expected: false – Reviel

Answer 2

/* Time complexity = O(n)*/

public static boolean isIsomorphic (String s1 , String s2){

    if (s1 == null || s2 == null){
        throw new IllegalArgumentException();
    }

    if (s1.length() != s2.length()){
        return false;
    }

    HashMap<Character, Character> map = new HashMap<>();

    for (int i = 0 ; i < s1.length(); i++){

        if (!map.containsKey(s1.charAt(i))){

            if(map.containsValue(s2.charAt(i))){

                return false;
            }           

            else{
                map.put(s1.charAt(i), s2.charAt(i));
            }           
        }
        else{
            if( map.get(s1.charAt(i)) != s2.charAt(i)){
                return false;                   
            }               
        }           
    }

    return true;        
}

Lianaliane

Answer 3

In your implementation, you will come to know of the answer only after processing both strings completely. While in many negative test cases, answer can be determined seeing the first violation itself.

For e.g. consider 1000 character long strings: "aa.." and "ba....". An elegant solution would have to return seeing the second character itself of two strings, as 'a' cannot map to both 'a' and 'b' here.

You may find this article helpful. It also points to a C++ based solution.

Important thing to note are:

• Since number of possible elements will be max pow(2, sizeof(char)), it is helpful to keep your own hash with ASCII code being the key itself. It gives significant improvement over the use of generic hash tables.

• In Case of C++, use of std::urordered_map is better than std::map and std::stl as the later one uses Balanced Binary Search trees only.

Showpiece

Nice to give an explanation about the main inefficiency in the OP. Also a very good observation that an array indexed by the character value allows direct lookup with perfect efficiency. A 0 value can be used to indicate "unmapped" without further ado. – Russellrusset

Answer 4

http://www.programcreek.com/2014/05/leetcode-isomorphic-strings-java/

You should be figuring out the algorithm by yourself though.

Goop

Answer 5

Two words are called isomorphic if the letters in single word can be remapped to get the second word. Remapping a letter means supplanting all events of it with another letter while the requesting of the letters stays unaltered. No two letters may guide to the same letter, yet a letter may guide to itself.

public bool isomorphic(string str1, string str2)
        {
            if (str1.Length != str2.Length)
            {
                return false;
            }

            var str1Dictionary = new Dictionary<char, char>();
            var str2Dictionary = new Dictionary<char, char>();
            var length = str1.Length;

            for (int i = 0; i < length; i++)
            {
                if (str1Dictionary.ContainsKey(str1[i]))
                {
                    if (str1Dictionary[str1[i]] != str2[i])
                    {
                        return false;
                    }
                }
                else
                {
                    str1Dictionary.Add(str1[i], str2[i]);
                }

                if (str2Dictionary.ContainsKey(str2[i]))
                {
                    if (str2Dictionary[str2[i]] != str1[i])
                    {
                        return false;
                    }
                }
                else
                {
                    str2Dictionary.Add(str2[i], str1[i]);
                }
            }

            return true;
        }

Naca

Answer 6

public class Isomorphic {

    /**
     * @param args
     */
    public static void main(String[] args) {
        // TODO Auto-generated method stub

        System.out.println(isIsomorphic("foo", "bar"));
        System.out.println(isIsomorphic("bar", "foo"));
        System.out.println(isIsomorphic("foo", "bar"));
        System.out.println(isIsomorphic("bar", "foo"));
        System.out.println(isIsomorphic("turtle", "tletur"));
        System.out.println(isIsomorphic("tletur", "turtle"));
        System.out.println(isIsomorphic("turtle", "tletur"));
        System.out.println(isIsomorphic("tletur", "turtle"));

    }

    public static boolean isIsomorphic(String s1,String s2) {

        if(s1.length()!=s2.length()) {
            return false;
        }

        if(s1.length()==1) {
            return true;
        }

        int c1;
        int c2;
        for(int i=0;i<s1.length()-1;i++) {
                    c1=s1.charAt(i);
                    c2=s1.charAt(i+1);
                if(c1==c2) {
                    c1=s2.charAt(i);
                    c2=s2.charAt(i+1);
                    if(c1==c2) {
                        continue;
                    }else {
                        return false;
                    }
                }else if(c1!=c2) {
                    c1=s2.charAt(i);
                    c2=s2.charAt(i+1);
                    if(c1!=c2) {
                        continue;
                    }else {
                        return false;
                    }
                }
        }

        return true;        
    }


}

Comments are welcome !!

Ipomoea

Answer 7

public bool IsIsomorphic(string s, string t)
{
    if (s == null || s.Length <= 1) return true;
    Dictionary<char, char> map = new Dictionary<char, char>();
    for (int i = 0; i < s.Length; i++)
    {
        char a = s[i];
        char b = t[i];
        if (map.ContainsKey(a))
        {
            if (map[a]==b)
                continue;
            else
                return false;
        }
        else
        {
            if (!map.ContainsValue(b))
                map.Add(a, b);
            else return false;

        }
    }
    return true;
}

Dunkirk

Answer 8

Here is my implementation...

private static boolean isIsmorphic(String string1, String string2) {

    if(string1==null) return false;
    if(string2==null) return false;
    if(string1.length()!=string2.length())return false;

    HashMap<Character,Character> map=new HashMap<>(); 
    for(int i=0;i<string1.length();i++){

        char c1=string1.charAt(i);
        char c2=string2.charAt(i);
        if(map.get(c1)!=null && !map.get(c1).equals(c2)){
            return false;
        }
        map.put(c1, c2);

    }

    return true;    
}

Seventy

Answer 9

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] m = new int[512];
        for (int i = 0; i < s.length(); i++) {
            if (m[s.charAt(i)] != m[t.charAt(i)+256]) return false;
            m[s.charAt(i)] = m[t.charAt(i)+256] = i+1;
        }
        return true;
    }
}

Consequently

Answer 10

I didn't find an answer without using Maps here, so posting my implementation which don't use additional memory. Actually using HashMap to check if words are isomorphic is very slow on short words. On my computer using the implementation is faster up to 20 symbols in test words.

static boolean isIsomorphic(String s1, String s2) {
    if (s1 == null || s2 == null) return false;

    final int n = s1.length();
    if (n != s2.length()) return false;

    for (int i = 0; i < n; i++) {
        final char c1 = s1.charAt(i);
        final char c2 = s2.charAt(i);
        for (int j = i + 1; j < n; j++) {
            if (s1.charAt(j) == c1 && s2.charAt(j) != c2) return false;
            if (s2.charAt(j) == c2 && s1.charAt(j) != c1) return false;
        }
    }

    return true;
}

Stumper

Answer 11

Java implementation using HashMap and HashSet. O(N) = n, O(S) = c, where c is the size of the character set.

boolean isIsomorphic(String s, String t){
    HashMap<Character, Character> map = new HashMap<>();
    HashSet<Character> set = new HashSet<>();
    if(s.length() != t.length())
        return false;
    for (int i = 0; i < s.length(); i++) {
        if(map.containsKey(s.charAt(i))){
            if(map.get(s.charAt(i)) != t.charAt(i))
                return false;
        } else if(set.contains(t.charAt(i))) {
            return false;
        } else {

            map.put(s.charAt(i), t.charAt(i));
            set.add(t.charAt(i));
        }
    }
    return true;
}

Beasley

Answer 12

There are many different ways on how to do it. Below I provided three different ways by using a dictionary, set, and string.translate.

Here I provided three different ways how to solve Isomorphic String solution in Python.

Wieland

Answer 13

This is the best solution I think

public boolean areIsomorphic(String s1,String s2)
{
    if(s1.length()!=s2.length())
    return false;
    
    int count1[] = new int[256];
    int count2[] = new int[256];
    
    for(int i=0;i<s1.length();i++)
    {
        if(count1[s1.charAt(i)]!=count2[s2.charAt(i)])
        return false;
        else
        {
            count1[s1.charAt(i)]++;
            count2[s2.charAt(i)]++;
        }
    }
    
    return true;
}

Monocyte

Could you explain a bit what makes your version the best solution? – Gertrude

Answer 14

C# soluation:

 public bool isIsomorphic(String string1, String string2)
    {

        if (string1 == null || string2 == null)
            return false;

        if (string1.Length != string2.Length)
            return false;

        var data = new Dictionary<char, char>();

        for (int i = 0; i < string1.Length; i++)
        {

            if (!data.ContainsKey(string1[i]))
            {

                if (data.ContainsValue(string2[i]))
                    return false;
                else
                    data.Add(string1[i], string2[i]);
            }
            else
            {
                if (data[string1[i]] != string2[i])
                    return false;
            }
        }

        return true;
    }

Tripalmitin

Answer 15

Here is my solution written in C++, the logic is based on comparing the indexes of each letter in both strings and compare whether they are equal. (If the indexes are equal then the letters are placed in the same place, in both cases)

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        if (s.length() != t.length()) return 0;

        for (int i = 0; i < s.length(); i++) {
            char l = s[i];
            vector<int> positions;

            for (int i2 = 0; i2 < s.length(); i2++) {
                if (s[i] == s[i2]) positions.push_back(i2);
            }

            char l2 = t[i];
            vector<int> positions2;
            for (int i3 = 0; i3 < t.length(); i3++) {
                if (t[i] == t[i3]) positions2.push_back(i3);
            }

            if (positions.size() != positions2.size()) return 0;

            for (int i4 = 0; i4 < positions.size(); i4++) if (positions[i4] != positions2[i4]) return 0;
        }

        return 1;
    }
};

Physiological