专栏首页爱写BugLeetCode 205:同构字符串 Isomorphic Strings

LeetCode 205:同构字符串 Isomorphic Strings

题目:

给定两个字符串 s*t*,判断它们是否是同构的。

如果 s 中的字符可以被替换得到 *t* ,那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换,同时保留字符的顺序。两个字符不能映射到同一个字符上,但字符可以映射自己本身。

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.

示例 1:

输入: s = "egg", t = "add"
输出: true

示例 2:

输入: s = "foo", t = "bar"
输出: false

示例 3:

输入: s = "paper", t = "title"
输出: true

说明: 你可以假设 s*t* 具有相同的长度。

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

解题思路:

在示例 3 中输入: s = "paper", t = "title",其中字母映射结果:p <==> t , a <==>i , e <==> l , r <==>e 映射的字母可以一一替换得到对应的单词,这便是同构字符串。

非同构字符串无非两种情况 (假设长度相等):

  • s = 'aa' , t = 'ab',在建立过字母映射 a <==> a 后,s 第二个字母 a 其映射 value = a 不等于 t 中第二个字母 b
  • s = 'ab' , t = 'aa',在建立过字母映射 a <==> b 后,t 第二个字母 a 其映射 key = a 不等于 s 中第二个字母 b

所以这个可以用两个哈希映射验证上述两种情况,也可以用一个映射加判断是否存在于其 values 中。

既然是建立映射字符,那么最先想到的就是哈希映射 (map、dict) 了。

该题为英文单词字符串同构检测,整个 ASCll 码长度才 256,所以这道题也可以用 char[256] 以索引值对应一个字符,其存储值对应一个字符建立映射关系。

还有一个更巧妙的解法,每个字符都与该字符串中第一次出现的索引对比是否相等,判断是否同构。如:

输入:s = 'aa' , t = 'ab'
第一次遍历:
s中第一个字符 a 第一次出现的索引为0,t中第一个字符 a 第一次出现的索引为0,索引相等,继续遍历
第二次遍历:
s中第二个字符 a 第一次出现的索引为0,t中第二个字符 b 第一次出现的索引为1,索引不相等, 返回false

代码:

双哈希映射:

Java:

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> s_map = new HashMap<>();
        Map<Character, Character> t_map = new HashMap<>();
        char[] s_chars = s.toCharArray(), t_chars = t.toCharArray(); // 转成 cahr 型数组
        for (int i = 0; i < s_chars.length; i++) {
            // 两种不成立的情况
            if (s_map.containsKey(s_chars[i]) && s_map.get(s_chars[i]) != t_chars[i]) return false;
            if (t_map.containsKey(t_chars[i]) && t_map.get(t_chars[i]) != s_chars[i]) return false;
            s_map.put(s_chars[i], t_chars[i]);
            t_map.put(t_chars[i], s_chars[i]);
        }
        return true;
    }
}

Python:

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        s_map, t_map = {}, {} # 双字典
        for c1, c2 in zip(s, t):
            # 两种不成立的情况
            if c1 in s_map and s_map[c1] != c2:
                return False
            if c2 in t_map and t_map[c2] != c1:
                return False
            s_map[c1] = c2
            t_map[c2] = c1
        return True

单哈希映射:

Java:

class Solution {
    public boolean isIsomorphic(String s, String t) {
        Map<Character, Character> map = new HashMap<>();// 一个哈希映射
        char[] s_chars = s.toCharArray(), t_chars = t.toCharArray();
        for (int i = 0; i < s_chars.length; i++) {
            if (map.containsKey(s_chars[i]) && map.get(s_chars[i]) != t_chars[i]) return false;
            // 判断t中字符是否存在于映射中的 values 内
            if (!map.containsKey(s_chars[i]) && map.containsValue(t_chars[i])) return false;
            map.put(s_chars[i], t_chars[i]);
        }
        return true;
    }
}

Python:

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        hash_map = {}
        for c1, c2 in zip(s, t):
            if c1 in hash_map and hash_map[c1] != c2:
                return False
            # 判断t中字符是否存在于映射中的 values 内
            if c1 not in hash_map and c2 in hash_map.values():
                return False
            hash_map[c1] = c2
        return True

字符首次出现的索引对比法:

Java:

class Solution {
    public boolean isIsomorphic(String s, String t) {
        char[] s_chars = s.toCharArray();
        char[] t_chars = t.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            // 判断该字符首次出现索引值是否相等
            if (s.indexOf(s_chars[i]) != t.indexOf(t_chars[i])) {
                return false;
            }
        }
        return true;
    }
}

Python:

class Solution:
    def isIsomorphic(self, s: str, t: str) -> bool:
        for c1, c2 in zip(s, t):
            # 判断该字符首次出现索引值是否相等
            if s.find(c1) != t.find(c2):
                return False
        return True

256 位字符映射

Java

class Solution {
    public boolean isIsomorphic(String s, String t) {
        char[] s_chars = s.toCharArray(), t_chars = t.toCharArray();
        char[] s_map = new char[256], t_map = new char[256]; //索引与存储值建立映射
        for (int i = 0; i < s_chars.length; i++) {
            char sc = s_chars[i], tc = t_chars[i];
            if (s_map[sc] == 0 && t_map[tc] == 0) {
                s_map[sc] = tc;
                t_map[tc] = sc;
            } else if (s_map[sc] != tc || t_map[tc] != sc) {//索引与元素值的映射是否满足条件
                return false;
            }
        }
        return true;
    }
}

python 中没有字符这一基础数据类型。

本文分享自微信公众号 - 爱写Bug(iCodeBugs),作者:爱写 Bug

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-10-16

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 387: 字符串中的第一个唯一字符

    给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。

    爱写bug
  • LeetCode 136:只出现一次的数字 Single Number

    给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。

    爱写bug
  • LeetCode 652: 寻找重复的子树 Find Duplicate Subtrees

    给定一棵二叉树,返回所有重复的子树。对于同一类的重复子树,你只需要返回其中任意一棵的根结点即可。

    爱写bug
  • Docker 常用命令

    用户1180017
  • iOS 堆栈符号解析最佳实践

    本文介绍了如何解析 iOS 的 crash 堆栈,分别使用了 symbolicatecrash 来自动解析整个堆栈,以及使用 atos 来解析单个地址的符号。 ...

    QQ空间开发团队
  • Xdebug 攻击面在 PhpStorm 上的现实利用

    在调试 Drupal 远程命令执行漏洞(CVE-2018-7600 && CVE-2018-7602)时,存在一个超大的数组 $form 。在该数组中寻找到注入...

    Seebug漏洞平台
  • 如何使用HBase存储文本文件

    Fayson
  • win10 uwp 去掉 Flyout 边框

    本文会经常更新,请阅读原文: https://lindexi.gitee.io/post/win10-uwp-%E5%8E%BB%E6%8E%...

    林德熙
  • Docker常用命令记录

    -t 选项是让docker分配一个伪终端(pseudo-tty)并绑定到容器的标准输入上

    用户2288853
  • mysql跨库关联查询(创建视图)

    我们使用的场景是:我们使用的是微服务架构,考虑的是模块划分,分为了业务配置服务,基础服务,业务服务等模块,数据库也进行了拆分,不同的模块使用不同的数据库。由于微...

    挑战者

扫码关注云+社区

领取腾讯云代金券