C#LeetCode刷题之#205-同构字符串(Isomorphic Strings)

C#LeetCode刷题之#205-同构字符串(Isomorphic Strings)

问题

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

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

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

输入: s = “egg”, t = “add”

输出: true

输入: s = “foo”, t = “bar”

输出: false

输入: s = “paper”, t = “title”

输出: true

说明:你可以假设 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.

Input: s = “egg”, t = “add”

Output: true

Input: s = “foo”, t = “bar”

Output: false

Input: s = “paper”, t = “title”

Output: true

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

示例

public class Program {

    public static void Main(string[] args) {
        var s = "egg";
        var t = "add";

        var res = IsIsomorphic(s, t);
        Console.WriteLine(res);

        Console.ReadKey();
    }

    private static bool IsIsomorphic(string s, string t) {
        var dic = new Dictionary<int, int>();
        for(var i = 0; i < s.Length; i++) {
            if(!dic.ContainsKey(s[i])) {
                if(dic.ContainsValue(t[i])) return false;
                dic[s[i]] = t[i];
            }
        }
        for(var i = 0; i < s.Length; i++) {
            if(dic[s[i]] != t[i]) return false;
        }
        return true;
    }

}

以上给出1种算法实现,以下是这个案例的输出结果:

True

分析:

该题解法参考 C#LeetCode刷题之#290-单词模式(Word Pattern)。

显而易见,以上算法的时间复杂度为: O(n)

本文由 .Net中文网 原创发布,欢迎大家踊跃转载。

转载请注明本文地址:https://www.byteflying.com/archives/3770

发表评论

登录后才能评论