83 ms Ruby DFS + Word Break I beats 100%


  • 0
    S

    Get references from different posts.

      
    

    def word_break(s, word_dict) return [] unless breakable?(s, word_dict) return dfs(s, word_dict, Hash.new{[]}) end

    def dfs(s, word_dict, memo) return memo[s] unless memo[s].empty? return [""] if s == "" result = [] word_dict.each do |word| list = [] if s.start_with?(word) list += dfs(s[word.length..-1], word_dict, memo) end list.each do |sub_word| result << (word + (sub_word.empty? ? "" : " ") + sub_word) end end memo[s] = result result end

    def breakable?(s, word_dict) return true if (s.nil? || s.empty?) && (word_dict.nil? || word_dict.empty?) return false if s.nil? || s.empty? || word_dict.nil? || word_dict.empty? dp = Array.new(s.length + 1) {false} dp[0] = true 1.upto(s.length) do |j| (j - 1).downto(0) do |i| if dp[i] && word_dict.include?(s[i...j]) dp[j] = true break end end end dp[s.length] end


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.