友链
姚屹晨

leetcode - [205] Isomorphic Strings

2020/04/21

题目描述

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

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.

You may assume both s and t have the same length.

判断两个字符串是否为同构字符串。

判断是否同构的标准：字母s是否能被字符t替代。

举几个例子：

Example 1:
Input: s = "egg", t = "add"
Output: true

Example 2:
Input: s = "foo", t = "bar"
Output: false

Example 3:
Input: s = "paper", t = "title"
Output: true

Example 4:
Input: s = "ab", t = "aa"
Output: false

Example 5:
Input: s = "ab", t = "ca"
Output: true

Update at 2020_0727

进阶题：

[890] Find and Replace Pattern

核心思想：

分别遍历两个字符串的当前字符，然后根据对应数组中的值，判断当前模式是否相等。

实现如下：

class Solution {
    public boolean isIsomorphic(String s, String t) {
        
        int N = 128;
        int n = s.length();
        int[] a1 = new int[N];
        int[] a2 = new int[N];
        
        char[] ch1 = s.toCharArray();
        char[] ch2 = t.toCharArray();
        
        for (int i = 0; i < n; i++){
            if (a1[ch1[i]] != a2[ch2[i]]){
                return false;
            }
            a1[ch1[i]] = a2[ch2[i]] = i + 1;
        }
        return true;
    }
}

Update at 2020_0628

类似题目：

[242] Valid Anagram
[290] Word Pattern

明确一下两者的区别：

Anagram：是指两个字符串拥有相同的字母，但是顺序不同，如：

s = "anagram", t = "nagaram"

Isomorphic：是指两个字符串是同形的，如：

s = "abb", t = "cdd"
  • 解法一 - HashMap & HashSet

和 [290] Word Pattern 这道题思路一样，借助HashMap与HashSet：

class Solution {
    public boolean isIsomorphic(String s, String t) {
        
        int len = s.length();
        HashMap<Character, Character> map = new HashMap<>();
        HashSet<Character> set = new HashSet<>();
        
        for (int i = 0; i < len; i++){
            char a = s.charAt(i);
            char b = t.charAt(i);
            if (map.containsKey(a)){
                if (map.get(a) != b) return false;
            } else {
                if (!set.add(b)) return false;
                map.put(a, b);
            }
        }
        return true;
    }
}
  • 解法二 - 正反法

Thanks LeetCode in Python 205 isomorphic strings - Michelle小梦想家

重新梳理下这道题：

这道题目的本质在于匹配两个字母的关系。

但是如何匹配呢？还有挺有讲究的。

举个例子： s = "bar", t = "foo"

此时，来看下匹配关系：

  • b -> f
  • a -> o
  • r -> o

从source的角度来看，都是一一匹配的。

但是从target的角度来看，明明o分别对应了a与r。

所以，我们还需要匹配一次： s = "foo", t = "bar"

此时：

  • f -> b
  • o -> a
  • o -> r

找到了不匹配的地方。

来看下实现：

class Solution {
    public boolean isIsomorphic(String s, String t) {
        
        return helper(s, t) && helper(t, s);
    }
    
    private boolean helper(String s, String t) {
        HashMap<Character, Character> map = new HashMap<>();
        int len = s.length();
        
        for (int i = 0; i < len; i++){
            char a = s.charAt(i);
            char b = t.charAt(i);
            if (map.containsKey(a) && map.get(a) != b){
                return false;
            }
            map.put(a, b);
        }
        return true;
    }
}

解法1

Thanks @grandyang

public boolean isIsomorphic(String s, String t) {    
    int[] a = new int[1 << 7];
    int[] b = new int[1 << 7];
    int n = s.length();
    for (int i = 0; i < n; i++){
        int x = s.charAt(i);
        int y = t.charAt(i);
        if (a[x] != b[y]) return false;
        a[x] = i + 1;
        b[y] = i + 1;
    }
    return true;
}

为什么要用i + 1，考虑如下场景：

Example 4:
Input: s = "ab", t = "aa"
Output: false

本质就是如何区分默认值0与自己赋值的0。

解法2

Thanks @yfcheng

public boolean isIsomorphic(String s, String t) {
    if (s.length() != t.length()) return false;
    Map<Character, Integer> m1 = new HashMap<>();
    Map<Character, Integer> m2 = new HashMap<>();
    
    for(Integer i = 0; i < s.length(); i++){
        char x = s.charAt(i);
        char y = t.charAt(i);
        if (m1.put(x, i) != m2.put(y, i)){
            return false;
        }
    }
    return true;
}

使用HashMap.put()方法，非常惊艳，因此它会返回相同key的old value！

还有一个点需要注意： Integer i = 0！

首先，需要提下JVM中有个整数池，当你比较-128 至 127之间的整数都是相等的(除了创建两个Integer对象)，如下：

Integer i1 = -128;
Integer i2 = -128;
System.out.println(i1 == i2); // true

Integer i3 = 127;
Integer i4 = 127;
System.out.println(i3 == i4); // true

Integer i5 = 128;
Integer i6 = 128;
System.out.println(i5 == i6); // false

因此当i = 128之前的整数都是没问题的，但当i = 128之后，发生了自动装箱，可以理解成创建了两个new Integer(128)的对象，所以old value不再相等。

HashMap<Character, Integer> map1 = new HashMap<>();
HashMap<Character, Integer> map2 = new HashMap<>();
Integer i128 = new Integer(128);
map1.put('c', 127);
map2.put('c', 127);
System.out.println(map1.get('c') == map2.get('c')); // true

map1.put('d', 128);
map2.put('d', 128);
System.out.println(map1.get('d') == map2.get('d')); // false

map1.put('e', i128);
map2.put('e', i128);
System.out.println(map1.get('e') == map2.get('e')); // true

Enjoy it!


一位喜欢提问、尝试的程序员

（转载本站文章请注明作者和出处 姚屹晨-yaoyichen）

Post Directory