[問題] LeetCode 472. Concatenated Words

[paneraii (沛納海)]

會 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://www.ptt.cc/bbs/Ruby/M.1540132253.A.EF1.html
推 johnlinvc: 你的演算法是 O(n^3) ，Array#include? 改用Set 試試？
推 mars90226: 感覺建立一個 trie，再查詢會比較快
→ mars90226: 建立時間複雜度O(n*m)，查詢是O(m)，n是數量，m是長度
→ mars90226: n*m應該不超過600000，m應該是60左右
推 matrixki: TLE就是算法不夠好 可以看discuss票數最高的最佳解
→ lance8537: 我ruby新手 用ruby刷題會有什麼困難點要注意嗎
推 b0w1d: 回樓上 時限有時候會很緊 一樣的算法用 C 寫會過 用 ruby