MaximumProductOfWordLengths [source code]


public class MaximumProductOfWordLengths {
static
/******************************************************************************/
class Solution {
    public int maxProduct(String[] words) {
        Arrays.sort(words, (a,b) -> b.length() - a.length());
        int[] masks = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            for (char c : words[i].toCharArray())
                masks[i] |= (1 << (c - 'a'));
        }
        int max = -1;
        for (int i = 0; i < words.length; i++) {
            for (int j = 0; j < i; j++) {
                if (words[j].length() * words[i].length() <= max)
                    break;
                if ((masks[i] & masks[j]) == 0) {
                    max = Math.max(max, words[i].length() * words[j].length());
                    break;
                }
            }
        }
        return max < 0 ? 0 : max;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        MaximumProductOfWordLengths.Solution tester = new MaximumProductOfWordLengths.Solution();
        String[][] inputs = {
            {"a","aa","aaa","aaaa"}, {"0"},
        };
    }
}

笨办法其实还是比较直接的, 就是所有的pair都做出来, 然后直接每一个pair进行一个处理, 但是每一个pair我们有两个操作内容, 首先要判断是否有overlapping, 然后再是算出来一个product; 问题是这个overlapping问题本身就不是特别好做; 这个问题的tag是bit, 这个刚开始自己想还真没有意识到往这个方向上面去想;

因为如果光是单纯的找overlapping这一件事情, 你都不见得很好做, 不可能到时候每一个pair里面的两个word都要做一个count, 然后再来对比count, 这最后的复杂度简直是无法形容的; 这个是一个Google的题目, 不可能让你最后写一个这么蠢的程序的;

这题最后想了半天还是没有思路, 放弃了;

上面代码是直接根据一个discussion最优解改编的, 加了一个pruning的优化; 这里还是要注意一下, bit操作的优先级很低, 所以各种括号不能少;

另外:

                masks[i] |= (1 <<< (c - 'a'));

这个这里这个<<<不行, 不知道为什么, 这个真的是不理解了;

另外, 注意这里的这个pruning:

注意这里有两个地方; 一个是发现当前的j即使成功, 也无法超越max的时候, 我们就直接放弃; 另外一个地方是当我们发现某一个j成功了之后, 直接放弃, 因为下面的j只会更小, 而i是固定不变的;
另外一个需要注意的地方是, 我们这里的exit用的应该是break, 而不是return, 也就是我们prune掉的只是当前的j, 而不是i; 仔细想想就知道为什么了: 比如我们在5 4的时候停掉了, 然后下一个i是4, 但是j的最大值可能是(length的最大值)比如10, 那么4 10仍然比5 * 4大, 所以当i改变之后还是有一个回弹的可能性的, 不能就直接return了;

最后的速度居然是115ms (25%), 很奇怪; 想想也是有可能的, 这个sort虽然没有增加复杂度, 但是不代表在倍数级别上面, 没有影响; 我们的这个pruning其实获得的也就是constant factor的改善, 所以最后这个pruning完全有可能没有带来任何的改进;

这个是discussion最优解:

public static int maxProduct(String[] words) {  
    if (words == null || words.length == 0)  
        return 0;  
    int len = words.length;  
    int[] value = new int[len];  
    for (int i = 0; i < len; i++) {  
        String tmp = words[i];  
        value[i] = 0;  
        for (int j = 0; j < tmp.length(); j++) {  
            value[i] |= 1 << (tmp.charAt(j) - 'a');  
        }  
    }  
    int maxProduct = 0;  
    for (int i = 0; i < len; i++)  
        for (int j = i + 1; j < len; j++) {  
            if ((value[i] & value[j]) == 0 && (words[i].length() * words[j].length() > maxProduct))  
                maxProduct = words[i].length() * words[j].length();  
        }  
    return maxProduct;  
}

然后是作者自己的解释:

ok,int has 32bits,but lower case letters only has 26 .we can use the lowest 26 bit of int indicates that the word has how many kinds of lower case letters .If the lowest bit of int is 1,it indicates the word has lower case letter 'a'.......the order of lower case letter is from right to left,like zyx.....cba.so value[i] indicates the condition of the word i having how many kinds of lower case letters .please vote me for this problem! If you have any question ,please follow up!

很多时候, 谈到bit的问题, 自己心里也是很没有底, 因为就算你都是知道了使用bit, bit本身可以被使用的方式也太多了; 今天晚上决定把那个bit的总结看一下, bit的题目吃亏已经吃的太多了;

这里这个问题, 首先其实不是一个重度依赖bit的东西, 不像以前的很多bit问题, 上来的思路就是直接做一个bit buckets, 火力全开的去做; 这里bit其实只是用来完成了一个很特殊的东西; 首先, 你可以看看他这个算法, 没有使用历史信息流, 主体程序其实还是穷搜(虽然缩小了j的搜索范围, 不过还是N^2); 他唯一做了的工作其实就是对所有的word进行了一个特殊的转化; 他这里总体的思路跟我自己想的笨办法是类似的, 但是他的实现更加聪明; 我当时卡住了就是因为想到, 先要搞N^2个pair出来, 然后每个pair还要进行一次overlapping的判断, 当时也没有具体去想这个overlapping怎么处理(直接count肯定可以, 但是很麻烦), 直接就认为这个整个思路都不可行; 但是实际上, 他这里这个算法, 最后唯一完成了优化的, 也就是处理overlapping这个成分, 其他的地方并没有做到很好的优化; 所以我感觉我这题的失败, 很大原因还是眼高手低, 先想了一个N^2的思路(没错, 就算用最简单的count, 最后其实也还是N^2), 感觉不行, 就直接思考N的思路, 实际上哪有N的思路呢; 我们说简单升级的思路, 从笨办法开始, 这个是对的, 但是你不能想完笨办法之后, 立刻就开始飞天要当神仙了; 简单升级的一个更大的核心技巧在于: 对于笨办法, 不是大概有思路就行了! 要非常细致的想到怎么实现(有时候甚至要写代码, 尤其是你对更加好的解法完全没有思路的情况下), 只有你这样做了之后, 你才能想到在这个想法的基础上去优化, 只有你对这个笨办法了解的够细致之后, 往往你才能够找到这个问题的intuition;

他这里这个算法, 其实就是一个很直接的优化; 比如两个word给你了, 要确定overlapping, 你最简单的怎么做? count, 用什么? 可以用HashMap. can we do better? 当然, 因为这里的domain是小写字母, 所以直接用hashing就可以, 这样每一个word有一个hashing的count array. 好了, 有了这两个array, 我们下面怎么处理? 这里就是我懒得去认真想的地方, 然而这题的优化点就是在这里了;

就算是你用普通的count的方法来做, 比如你有[0,1,2]和[1,1,0], 那么你怎么确定有overlapping? 可以每一个index位置乘一下, 然后全部加起来就行了, 因为我们追求的是: the same index at both arrays can't both be non-zero.

而这里这个算法的思路, 就是对这个思路进行的优化; 首先, 这里的2, 我们其实可以只用1就行了: 我们在乎的不是count, 而是occurrence, 只要有一个就可以了; 当你看到这个的时候, 你看到了什么? 对全都是0,1, 那么这里的bit的操作的思路就呼之欲出了;

事实上我不觉得这个思路比我的笨办法直接hashing然后乘法快很多, 不过反正也是一个思路吧; 尤其是处理no overlapping的时候, 以后你应该有思路了, 这个估计还是一个比较general的需求; 如果domain有限, 就可以用这里这个bit flag的思路, 否则的话, 直接count的做法也可以; 对了, 如果是domain很大的情况下, 我感觉直接用set做好像更简单一些? 每个word给一个set; 当然这样一个做法, 最后的缺点就是空间复杂度会比较大, 也许这个就是这里的这个bit做法的优势所在;

这题还是很可惜的, 这个hashing的方法按理应该想出来的;

另外, 还是关于开头的Empty case的判断:

"words == null" means you haven't allocate any memory to it. (i.e. "words" is a null pointer)..."words.length == 0" means "words" points to a memory block but there is nothing in it. If you only write "words.length == 0" in the if statement and "words" turns out to be a null pointer, the program will throw NullPointerException.

这一方面我最近还是很生疏; 不要想着什么我实际上面试的时候就知道去写了, 这都什么时候了, 你做的每一道题目都应该当做面试去做了;

这个是另外一个解法:

public class Solution {  
    public int maxProduct(String[] words) {  
        int max = 0;  

        Arrays.sort(words, new Comparator<String>(){  
            public int compare(String a, String b){  
                return b.length() - a.length();  
            }  
        });  

        int[] masks = new int[words.length]; // alphabet masks  

        for(int i = 0; i < masks.length; i++){  
            for(char c: words[i].toCharArray()){  
                masks[i] |= 1 << (c - 'a');  
            }  
        }  

        for(int i = 0; i < masks.length; i++){  
            if(words[i].length() * words[i].length() <= max) break; //prunning  
            for(int j = i + 1; j < masks.length; j++){  
                if((masks[i] & masks[j]) == 0){  
                    max = Math.max(max, words[i].length() * words[j].length());  
                    break; //prunning  
                }  
            }  
        }  

        return max;  
    }  
}

看起来一开始的这个sorting虽然不影响复杂度, 但是是多余的, 很蠢, 但是实际上不是这样的;

That's what sorting is for. So that you can exit if squaring is not larger than the max. Because if you keep going, the product will not get larger.

谈到算法加速, 不要脑子里面立刻想出来的只有各种复杂度的讨论; 尤其是类似pruning这种非线性的优化, 很多时候在实际的速度上能够产生质变;

这个是一个很有意思的新思路:

@StefanPochmann said in Bit shorter C++:

Same algorithm as most, just written a bit shorter.

int maxProduct(vector<string>& words) {  
    vector<int> mask(words.size());  
    int result = 0;  
    for (int i=0; i<words.size(); ++i) {  
        for (char c : words[i])  
            mask[i] |= 1 << (c - 'a');  
        for (int j=0; j<i; ++j)  
            if (!(mask[i] & mask[j]))  
                result = max(result, int(words[i].size() * words[j].size()));  
    }  
    return result;  
}

Update: Here's an O(n+N) variation, where n is the number of words and N is the total number of characters in all words. Thanks to junhuangli for the suggestion.

int maxProduct(vector<string>& words) {  
    unordered_map<int,int> maxlen;  
    for (string word : words) {  
        int mask = 0;  
        for (char c : word)  
            mask |= 1 << (c - 'a');  
        maxlen[mask] = max(maxlen[mask], (int) word.size());  
    }  
    int result = 0;  
    for (auto a : maxlen)  
        for (auto b : maxlen)  
            if (!(a.first & b.first))  
                result = max(result, a.second * b.second);  
    return result;  
}

Or: (thanks to junhuangli's further comment)

int maxProduct(vector<string>& words) {  
    unordered_map<int,int> maxlen;  
    int result = 0;  
    for (string word : words) {  
        int mask = 0;  
        for (char c : word)  
            mask |= 1 << (c - 'a');  
        maxlen[mask] = max(maxlen[mask], (int) word.size());  
        for (auto maskAndLen : maxlen)  
            if (!(mask & maskAndLen.first))  
                result = max(result, (int) word.size() * maskAndLen.second);  
    }  
    return result;  
}

下面的那两个优化还是挺有意思的, 尤其是第一个优化; 这个人其实就是注意到了, 我们最后当采用了这个bit flag的思路来处理overlapping之后, 最后比较麻烦的部分其实是最后这个每个pair一个比较的部分; 我们最后给每一个word获得了一个mask之后, 要每一个pair的word之间进行一个mask的计算; 这里他的优化其实是进一步的避免overkill: 我们最后需要的其实是最大的一个长度乘积; 计算这个最大乘积所需要的最小信息量是什么? 我们需要的其实是所有的最大长度就行了, 以及对应这个最大长度的一个mask, 这样我们知道这两个长度可以相乘; 这么讲可能还是有点模糊, 不过最后这个优化的核心就是观察到这里的这个规律, 然后事实情况是, 一个length可能对应多个mask, 所以直接用(mask, max_length)的Map来保存更好;

至于这里生成的linear的复杂度, 其实是有一点hackish的, 因为这个其实最后依靠的就是, mask的总数是固定的(2^26)个. 当然, 严格意义上来说, 这个也没错, 毕竟Integer.MAX_VALUE都是一个constant, 2^26当然更应该是; //比2^32要大;

第二个优化其实不是特别值得研究, 其实就是一个整合到一个pass的做法, 有空看看可以, 不过对于readability并没有帮助;

@junhuangli said in Bit shorter C++:

create a hash table using your mask as key, and the max length as value.
Since the max size this hash table can go is a constant(26 ones). This algorithm will be o(n)

没有优化过的做法, 你需要对each pair of the n words进行比较, 这个是跟n有关的; 优化了之后, 你只需要对each pair of the 2^26 masks进行比较, 这个是可以理解为是一个constant;

there are at most 2^26 possible value, yeah it is really big, but it is still O(1), as StefanPochmann puts it.
As wiki says " When expressed this way, the time complexity is said to be described asymptotically, i.e., as the input size goes to infinity."

另外, 这个问题本来的contributor自己居然也不认同这个linear:

I don't think so. It will not be O(n).
In the worst case, none of two words have the same mask. You will not save anything with your hash table.

但是他这里还是犯了一个错误, 他没有意识到numeber of distinct masks是有上限的;

discussion其他的解法基本都和这个差不多了;

Problem Description

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.

Example 1:

Given ["abcw", "baz", "foo", "bar", "xtfn", "abcdef"]  
Return 16  
The two words can be "abcw", "xtfn".

Example 2:

Given ["a", "ab", "abc", "d", "cd", "bcd", "abcd"]  
Return 4  
The two words can be "ab", "cd".

Example 3:

Given ["a", "aa", "aaa", "aaaa"]  
Return 0  
No such pair of words.

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Difficulty:Medium
Total Accepted:52.5K
Total Submissions:118.4K
Contributor: LeetCode
Companies
google
Related Topics
bit manipulation

LC318 MaximumProductOfWordLengths

MaximumProductOfWordLengths [source code]

Problem Description

results matching ""

No results matching ""