Ruby Solution - Bit Operation

  • 0

    The crux of this problem is to solve

    where the two words do not share common letters

    As the word only contains a-z, we can use 26 bits to represent the letters each word consists of. For example, we can turn word hello into an integer whose binary form is

    00000000000100100010010000 # => 18576

    To check whether two words share common letters, we can use & bit operation in an efficient way.

    In addition, to avoid TLE we need to

    1. Pre-process each word to get its binary form, instead of calculating it on the run.
    2. Sort the words by length, then pruning the small product. This is crucial for a Ruby script to pass this problem.
      def max_product(words)
        words = words.sort_by(&:length).reverse
        # 1. Pre-process each word into binary forms
        bins = do |word|
          word.chars.reduce(0){|val, ch| val |= 1 << (ch.ord - 'a'.ord) }
        max = 0
        words.each_with_index do |a, i|
          # 2. It'll be TLE without this pruning
          next if a.length * a.length <= max
          words[i+1..-1].each_with_index do |b, j|
            next if (bins[i] & bins[i+1+j]).nonzero?
            max = [ max, a.length * b.length ].max

Log in to reply

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