recursive ruby solution in 7 lines


  • 1
    A
    def word_break(s, dict)
      return true if s == ''
      dict.each do |word|
        next unless word == s[0...word.size]
        return true if word_break(s[word.size..-1], dict)
        dict.delete(word)
      end
      false
    end
    

  • 0
    def word_break(s, dict)
      return true if s == ''
      dict.each do |word|
        if s.start_with?(word)
            return true if word_break(s[word.size..-1], dict)
            dict.delete(word)
        end
      end
      false
    end
    

    Use start_with instead of creating a new string slightly improves the performance.


  • 0

    Could you explain why you delete the word at the end of each loop?

    dict.delete(word)
    

    I think I may found a edge case that break this algorithm:

    word_break("catscatdog", Set.new(["cat", "cats", "dog"]))
    # Actual: False
    # Expected: True
    

    This one will work though. It seems like this algorithm has dependency on the order in which we iterate the word_dict set.

    word_break("catscatdog", Set.new(["cats", "cat", "dog"]))
    # Actual: True.
    # Expected: True
    

Log in to reply
 

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