Ruby Solution - Bit Operation


  • 0
    I

    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

    zyxwvutsrqponmlkjihgfedcba
    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 = words.map do |word|
          word.chars.reduce(0){|val, ch| val |= 1 << (ch.ord - 'a'.ord) }
        end
    
        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
          end
        end
    
        max
      end
    

Log in to reply
 

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