同构字符串

Question

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

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

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

例如，假设 "egg"、"add"、return 为真。

鉴于 "foo"、"bar"、return 错误。

鉴于 "paper"、"title"、return 正确。

注意：您可以假设 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

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

虽然你应该自己弄清楚算法。

Answer 2

如果单个单词中的字母可以重新映射得到第二个单词，则两个单词称为同构。重新映射一个字母意味着用另一个字母替换它的所有事件，同时对字母的请求保持不变。没有两个字母可以指向同一个字母，但一个字母可以指向自己。

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 3

在您的实现中，只有在完全处理这两个字符串后您才会知道答案。而在许多负面测试用例中，可以通过查看第一个违规本身来确定答案。

例如考虑 1000 个字符长的字符串："aa.." 和 "ba...."。一个优雅的解决方案是 return 看到两个字符串的第二个字符本身，因为 'a' 不能同时映射到 'a' 和 'b'。

您可能会发现 this article 有帮助。它还指向基于 C++ 的解决方案。

需要注意的重要事项是：

由于可能元素的数量将是最大 pow(2, sizeof(char))，因此使用 ASCII 码本身作为密钥来保留您自己的哈希值会很有帮助。它比使用通用哈希表有显着改进。
对于 C++，使用 std::urordered_map 优于 std::map 和 std::stl，因为后者仅使用平衡二叉搜索树。

Answer 4

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

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 == '[=10=]' && character2 == '[=10=]') {
                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 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;
}

Answer 10

我没有在这里使用地图找到答案，所以发布我的不使用额外内存的实现。实际上使用 HashMap 检查单词是否同构在短单词上非常慢。在我的计算机上，使用该实现在测试单词中最多可使用 20 个符号。

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

Answer 11

Java 使用 HashMap 和 HashSet 实现。 O(N) = n, O(S) = c，其中c是字符集的大小。

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

Answer 12

有很多不同的方法可以做到这一点。下面我通过使用字典、集合和 string.translate.

提供了三种不同的方式

Answer 13

这是我认为最好的方案

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

Answer 14

C# 解决方案：

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

同构字符串

Isomorphic Strings

string

hashmap

set

data-structures