同构字符串[简单]-Toy模板网

这篇具有很好参考价值的文章主要介绍了同构字符串[简单]。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

优质博文：IT-BLOG-CN

一、题目

给定两个字符串s和t，判断它们是否是同构的。如果s中的字符可以按某种映射关系替换得到t，那么这两个字符串是同构的。每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

示例 1:
输入：s = "egg", t = "add"
输出：true

示例 2：
输入：s = "foo", t = "bar"
输出：false

示例 3：
输入：s = "paper", t = "title"
输出：true

1 <= s.length <= 5 * 104
t.length == s.length
s和t由任意有效的ASCII字符组成

二、代码

思路： 判断s和t每个位置上的字符是否都一一对应，即s的任意一个字符被t中唯一的字符对应，同时t的任意一个字符被s中唯一的字符对应。这也被称为「双射」的关系。以示例2为例，t中的字符a和r虽然有唯一的映射o，但对于s中的字符o来说其存在两个映射{a,r}，故不满足条件。

因此，我们维护两张哈希表，第一张哈希表s2t以s中字符为键，映射至t的字符为值，第二张哈希表t2s以t中字符为键，映射至s的字符为值。从左至右遍历两个字符串的字符，不断更新两张哈希表，如果出现冲突（即当前下标index对应的字符s[index]已经存在映射且不为t[index]或当前下标index对应的字符t[index]已经存在映射且不为s[index]时说明两个字符串无法构成同构，返回false。如果遍历结束没有出现冲突，则表明两个字符串是同构的，返回true即可。

class Solution {
    public boolean isIsomorphic(String s, String t) {
        // 创建2个hashMap，key为s的字符，value为t字符，另一个正好相反
        if (s == null || t == null || s.length() != t.length()) {
            return false;
        }
        Map<Character,Character> s2t = new HashMap();
        Map<Character,Character> t2s = new HashMap();
        for (int i = 0; i < s.length(); i++) {
            Character si = s.charAt(i);
            Character ti = t.charAt(i);
            if ((s2t.containsKey(si) && !ti.equals(s2t.get(si))) || (t2s.containsKey(ti) && !si.equals(t2s.get(ti)))) {
                return false;
            }
            s2t.put(si,t.charAt(i));
            t2s.put(ti,s.charAt(i));
        }
        return true;
    }
}

时间复杂度： O(n)其中n为字符串的长度。我们只需同时遍历一遍字符串s和t即可。
空间复杂度： O(∣Σ∣)其中Σ是字符串的字符集。哈希表存储字符的空间取决于字符串的字符集大小，最坏情况下每个字符均不相同，需要O(∣Σ∣)的空间。文章来源地址https://www.toymoban.com/news/detail-739219.html

到了这里，关于同构字符串[简单]的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！