同構字符串

Question

給定兩個字符串s和t，確定它們是否是同構的。

如果s中的字符可以被替換以獲得t，那麼兩個字符串是同構的。

所有出現的字符都必須用另一個字符替換，同時保留字符的順序。沒有兩個角色可以映射到相同的角色，但角色可以映射到自己。例如， 給定「egg」，「add」，返回true。

給出「foo」，「bar」，返回false。

鑑於「紙」，「標題」，返回true。

注意： 你可以假設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

這是另一個實現，但內存使用較少。

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

Answer 2

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

你應該自己雖然被搞清楚的算法。

Answer 3

如果單個單詞中的字母可以重新映射以獲得第二個單詞，則稱兩個單詞爲同構。重新制作一封信意味着用另一封信替代它的所有事件，而請求信件保持不變。沒有兩封信可以引導到同一封信，但一封信可能會引導自己。

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

Answer 4

在你的實現中，只有在完全處理完兩個字符串後，你纔會知道答案。雖然在很多負面的測試案例中，答案可以通過查看第一次違規本身來確定。

例如，考慮1000個字符長的字符串：「aa ..」和「ba ....」。一個優雅的解決方案將不得不返回看到兩個字符串的第二個字符本身，因爲'a'在這裏不能映射到'a'和'b'。

您可能會感興趣this article對您有所幫助。它也指向一個基於C++的解決方案。

要注意的重要一點是：

• 由於可能的要素的數量將是最大POW（2的sizeof（炭）），它有助於保持你自己的哈希與ASCII碼是關鍵本身。它比使用通用哈希表提供了重大改進。

• 在C++的情況下，使用std :: urordered_map比std :: map和std :: stl更好，因爲後者僅使用平衡二叉搜索樹。

Answer 5

/*時間複雜度= 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 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;   
    } 


} 

評論，歡迎！

Answer 7

這是我實現......

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

Answer 8

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

Answer 9

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