当前位置: 首页 > 后端技术 > Node.js

Leetcode242字谜的三种有效解法

时间:2023-04-03 14:30:58 Node.js

背景中午看到这道题。这是一个简单的问题。我用了几种方法来做到这一点,我会告诉你们。题目描述:给定两个字符串s和t,写一个函数判断t是否是s的变位词。示例1:输入:s="anagram",t="nagaram"输出:true示例2:输入:s="rat",t="car"输出:false解释:你可以假设字符串只包含小写字母.文字题目比较简单,属于那种一眼就能看出来的思路。我用了三种方案,大家可以尝试一些其他的方法来拓宽思路。方案一:暴力排序/***@param{string}s*@param{string}t*@return{boolean}*///方案一:暴力排序,NLognvarisAnagram=function(s,t){returns.split('').sort().join('')==t.split('').sort().join('')};第一种方案最容易想到,也是最暴力的:对字符串进行排序比较。在这个方法中,时间复杂度是O(NlogN)。面试的时候直接写这个,怕是直接被刷了,哈哈。方案二:设置这个方法也很简单。直接数字母的个数。遍历两组字符串时,一组用于加法,另一组用于减法。如果之后集合中的数字都为0,则说明两对是偏移的,是合法的anagram。否则,它不是。因为a的ASCII对应97,b的就是98,以此类推。减去97后,a放在array[0],b放在array[1],以此类推。26个字母存放在一个长度为26的集合中,最后遍历这个集合的数字全部为0。这种方法的时间复杂度为O(N),比第一种方法要好。代码实现,//方法二:SetvarisAnagram=function(s,t){if(s.length!==t.length)returnfalse;varary=newArray(26).fill(0);for(vari=0;i