登录
  • #刷题

由一‌‌‍‍‌‍‌‌‌‌‍‍‌‍‌‍‍‌‍‌‍‌‌‌‍‍‍‌‌‍‍‍道easy题引发的思考

lijiahao5269588
411
0
传送门 leetcode.com

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

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

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

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



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

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

发表回复