
问题
给定两个字符串 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)。
显而易见,以上算法的时间复杂度为: 。
本文由 .Net中文网 原创发布,欢迎大家踊跃转载。
转载请注明本文地址:https://www.byteflying.com/archives/3770。