查看: 489|回复: 0
收起左侧

[Leetcode] 由一道easy题引发的思考

|只看干货
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   100% (1)
 
 
0% (0)    👎

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
传送门  https://leetcode.com/problems/ch ... ays-are-equivalent/

题目很简单,给两个 string 数组,判断两个数组中的 string 分别首尾拼接在一起后,得到的结果是否相同。

这个题官方没有给 solution,看了 discussion 大多数解法就是按照字面意思通过 string 或者 stringbuilder 的方法得到最终结果进行比较。

这样的话首先进行了首尾拼接,会消耗 O(N) 时间复杂度,其次拼接完的字符串再进行比较也会消耗 O(N),虽然最后结果是 O(N) 但其实走了三遍(两个数组每个数组拼接一次,最后比较一次,一共三次)。其次用字符串保存结果也会消耗 O(N) 的空间复杂度。更重要的是,这个方法不管最后结果如何,都必须全部拼接完才能进行比较。

那么有没有更快更省空间的方法呢?我想要知道最后结果是不是一样的,其实最好的方法是挨个比较每个字符,这样一旦出现两个字符不同的情况,立刻就能返回 false,而不需要全部比较完。可是给定的两个字符串数组,他们长度可能不同,其中每个字符串也不相同,如何每次得到他们的下一个字符进行比较呢?我们其实可以实现一个 iterator,对于一个字符串数组而言,我每次 next() 返回的是下一个应该出现的字符。对于这样的一个迭代器,其实只需要维护两个指针,一个指向当前的字符串,一个指向该字符串中的某个字符,然后根据字符串的长度进行迭代即可,代码见图片。

image.png



可以看到,iterator 的构造器传入了这个字符串数组,但是注意这里传的其实只是对原数组的一个引用,因此并没有耗费额外空间。从时间上来讲,两个 iterator 可以保证每次迭代同时处理两个字符串数组(如果你用 string 构造的方法,那就必须先构造 a,再构造 b,实际上走了两遍),而且遇到不一样的字符串可以立即终止,不需要全部跑完。

其实这个方法没有什么高深的技巧可言,对性能提升也是微乎其微。但是如果这道题出现在真正的面试中,难道会单纯的考大家字符串拼接的代码吗?有时候总是能看到不刷 easy 的言论,但楼主认为,leetcode 上面的 easy 主要是 easy 在能让人一眼看出怎么做。但是要得到最优解,可能还需要更多的思考。

评分

参与人数 1大米 +15 收起 理由
14417335 + 15

查看全部评分


上一篇:零基础刷题犯错给大家乐乐
下一篇:找后端开发实习对SDE有帮助吗
您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表