Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Isomorphic Strings

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;
    }
like image 401
ojas Avatar asked Jun 27 '15 07:06

ojas


People also ask

What are isomorphic words?

Two strings are called isomorphic if the letters in one string can be remapped to get the second string. Remapping a letter means replacing all occurrences of it with another letter but the ordering of the letters remains unchanged. No two letters may map to the same letter, but a letter may map to itself.

What is isomorphic string Java?

The string is called isomorphic if the letters of the one string can be mapped to get the second string. Mapping means replacing all occurrences of a letter with another letter but the ordering of the letters remains unchanged. Note that no two letters may map to the same letter but a letter may map to itself.

What is isomorphic string python?

Two strings str1 and str2 are called isomorphic if there is a one-to-one mapping possible for every character of str1 to every character of str2. And all occurrences of every character in 'str1' map to the same character in 'str2'.

How do you check if two strings are isomorphic or not?

Two strings are isomorphic if one-to-one mapping is possible for every character of the first string to every character of the second string. For example, consider the two strings: “ACAB” and “XCXY”. We can map the characters of the first string to the characters of the second string as follows: 'A' maps to 'X'.


1 Answers

/* 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;        
}
like image 74
Gökhan Akduğan Avatar answered Nov 04 '22 21:11

Gökhan Akduğan