Problem:
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.
Subscribe to see which companies asked this question
Solutuion: 关键词 位操作
class Solution { public: int maxProduct(vector<string>& words) { // 解题思路：用一个26位来表示每个字符串字母出现的情况 若出现则字母对应的为为1 前期预处理过程 //本题只关心字母是否出现过 if(words.empty() || words.size()==0) return 0; //字母预处理 vector<int> processwords(words.size(),0); for(int i=0;i<words.size();i++) { string temp_str=words[i]; for(int j=0;j<temp_str.length();j++) processwords[i]|=1<<(temp_str[j]-‘a‘); } int maxproduct=0; for(int i=0;i<words.size()-1;i++) for(int j=i+1;j<words.size();j++) if((processwords[i]&processwords[j])==0) { int len=words[i].length()*words[j].length(); maxproduct=max(maxproduct,len); } return maxproduct; } };
原文：http://www.cnblogs.com/xiaoying1245970347/p/5131754.html