同构字符串

问题描述

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

Given two strings s and t, determine if they are isomorphic.

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

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.

例如，
给定 egg， add，返回true 。

For example,Given "egg", "add", return true.

给出 foo， bar，返回false。

Given "foo", "bar", return false.

给出 paper， title

Given "paper", "title", return true.

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

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

推荐答案

这是另一个实现，较少的内存使用。

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

这篇关于同构字符串的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！