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)$ 。

巴特西

C#LeetCode刷题之#205-同构字符串（Isomorphic Strings）

最新文章

热门文章