同构字符串

Question

给定两个字符串 s 和 t，确定它们是否同构。

如果 s 中的字符可以替换为 t，则两个字符串是同构的。

所有出现的字符都必须替换为另一个字符，同时保留字符的顺序。没有两个字符可以映射到同一个字符，但一个字符可以映射到它自己。

例如，给定“egg”、“add”，返回 true。

给定“foo”、“bar”，返回false。

给定“论文”、“标题”，返回真。

注意：您可以假设 s 和 t 的长度相同。

我有这个解决方案，但它花费了太多时间。任何好的解决方案将不胜感激

   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;
    }

Answer 1

/* 时间复杂度 = 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;        
}

Answer 2

这是另一种实现，但内存使用量较少。

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
    }
}