作者paneraii (沛纳海)
看板Ruby
标题[问题] LeetCode 472. Concatenated Words
时间Sun Oct 21 22:30:51 2018
会 time limit exceeded，求高手指点
def find_all_concatenated_words_in_a_dict(words)
return [] if words.count <= 1 || words.count > 10000 || words.map(&:to_s).inject(&:+).length > 600000
result = []
[*0...words.count].each do |i|
new_arr = words.dup
new_word = new_arr.delete(words[i]).dup
result << words[i] if concated_by_others?(new_word, new_arr)
end
return result
end
def concated_by_others?(str, arr)
[*1..str.length].each do |j|
if arr.include?(str.slice(0, j))
new_str = str.dup
new_str.slice!(str.slice(0, j))
return true if new_str.length.zero? or concated_by_others?(new_str, arr)
end
end
return false
end
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 36.228.105.126
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Ruby/M.1540132253.A.EF1.html
1F：推 johnlinvc: 你的演算法是 O(n^3) ，Array#include? 改用Set 试试？ 10/21 23:10
2F：推 mars90226: 感觉建立一个 trie，再查询会比较快 10/21 23:13
3F：→ mars90226: 建立时间复杂度O(n*m)，查询是O(m)，n是数量，m是长度 10/21 23:14
4F：→ mars90226: n*m应该不超过600000，m应该是60左右 10/21 23:15
5F：推 matrixki: TLE就是算法不够好 可以看discuss票数最高的最佳解 10/22 02:42
6F：→ lance8537: 我ruby新手 用ruby刷题会有什麽困难点要注意吗 05/16 13:07
7F：推 b0w1d: 回楼上 时限有时候会很紧 一样的算法用 C 写会过 用 ruby 05/17 13:35