当前位置: 首页 > Web前端 > JavaScript

Go&Java算法同构字符串

时间:2023-03-27 14:20:39 JavaScript

同构字符串给定两个字符串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*104t.length==s.lengths和t由任意有效的ASCII字符组成方法一:哈希表(Java)这道题需要我们判断s和t各位置的字符是否一一对应,即s的任意字符对应t中的唯一字符,t的任意字符对应s中的唯一字符。这也称为“双射”关系。以例2为例,虽然字符a和r在t中有唯一的映射o,但是s中的字符o有两个映射{a,r},所以不满足条件。因此,我们维护两个哈希表,第一个哈希表s2t以s中的字符为键,映射到t的字符为值,第二个哈希表t2s以t中的字符为键,映射到t中的字符s字符是值。classSolution{publicbooleanisIsomorphic(Strings,Stringt){Maps2t=newHashMap();Mapt2s=newHashMap();intlen=s.length();对于(inti=0;i0&&s2t[x]!=y||t2s[y]>0&&t2s[y]!=x{returnfalse}s2t[x]=yt2s[y]=x}returntrue}时间复杂度:O(N)空间复杂度:O(1)