205. Isomorphic Strings 同构字符串

题目地址：https://leetcode.com/problems/isomorphic-strings/#/descriptionopen in new window

题目描述

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

Twostrings are isomorphic if the characters in s can be replaced to get t.

Alloccurrences 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.

题目大意

看s到t的映射关系是不是一一映射的，s中不同的字符是不能映射到t的同一个字符的。

解题方法

字典保存位置

这个题可以看出来使用hashmap，但是，注意的一点是不要用位置++的方式，这样的话只统计了这个字符出现的次数，没有统计对应的位置，导致出错。比如aba和baa就会导致结果错误。因此，用到的是字符出现的位置+1的方式，保证能在hash位置处保存字符出现的位置。

public class Solution {
    public boolean isIsomorphic(String s, String t) {
        int[] m1 = new int[256];
        int[] m2 = new int[256];
        int len = s.length();
        for(int i = 0; i < len; i++){
            if(m1[s.charAt(i)] != m2[t.charAt(i)]){
                return false;
            }
            m1[s.charAt(i)] = i + 1;
            m2[t.charAt(i)] = i + 1;
        }
        return true;
    }
}

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

字典保存映射

因为是一一映射关系，所以s到t和t到s的映射都要进行判断。最简单的方法就是使用两次判断，这样的话，我们可以分别看映射关系是不是一致的。

class Solution(object):
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        m = dict()
        for i, c in enumerate(s):
            if c in m:
                if t[i] != m[c]:
                    return False
            else:
                m[c] = t[i]
        m = dict()
        for i, c in enumerate(t):
            if c in m:
                if s[i] != m[c]:
                    return False
            else:
                m[c] = s[i]
        return True

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

既然想到了两次判断，那么我们应该也能想到，使用两个字典分别保存s到t的判断和t到s的判断。代码如下：

class Solution(object):
    def isIsomorphic(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: bool
        """
        m = dict()
        n = dict()
        for i, c in enumerate(s):
            if c in m and m[c] != t[i]:
                return False
            if t[i] in n and c != n[t[i]]:
                return False
            m[c] = t[i]
            n[t[i]] = c
        return True

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有

本文经作者：负雪明烛授权发布，任何组织或个人未经作者授权不得转发