Algorithm

每日一题-字符串乘积

[每日一题] (字符串乘积)
Given a list of words, return the maximum numerical product value of two words length, where the two words don’t share any common letters.
For this example, [cat, dog, day, space, telephone]
cat->3 and telephone->9, return 3X9=27

解题思路


这题暂时没什么好的思路，唯一想到可以优化的地方就是可以使用bit manipulation来判断字符是否重复。
可以使用32为二进制数来代表每个单词(假设26个字母), 判断字符是否重复时就直接与运算判断是否为0。
剩下的用Brute Force

Python:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#!/usr/bin/env python
# -*- coding:utf-8 -*-
words = ["cat", "dog", "day", "space", "telephone"]
class Solution(object):
    def wordMul(self, words):
        n = len(words)
        bit = [0 for i in xrange(n)] # binary number for each word
        wl = [len(words[i]) for i in xrange(n)] # length of each word
        self.produceBit(words, bit, wl)
        maximum = 0
        for i in xrange(n-1):
            for j in xrange(i, n):
                if bit[i] & bit[j] == 0:
                    maximum = max(maximum, wl[i] * wl[j])
        return maximum
    def produceBit(self, words, bit, wl):
        alpha = "abcdefghijklmnopqrstuvwxyz"
        dict = {}
        for i in xrange(len(alpha)):
            dict[alpha[i]] = i 
        for i in xrange(len(words)):
            for j in xrange(wl[i]):
                d = dict[words[i][j]]
                bit[i] = bit[i] | 1 << d