# 318. Maximum Product of Word Lengths

## 描述

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

## 分析

1.穷举法

class Solution {
public:
int maxProduct(vector<string>& words) {
int max=0;
for(int i=0;i<words.size();i++){
int k=0;
int map[26]={0};
int size_a=words[i].size();
while(k<words[i].size())
map[words[i][k++]-'a']=1;
for(int j=i+1;j<words.size();j++){
int m=0;
int size_b=words[j].size();
if(size_a*size_b>max){
while(m<words[j].size()){
if(map[words[j][m]-'a']==0)
m++;
else
break;
}
if(m==words[j].size())
max=size_a*size_b;
else
continue;
}
}
}
return max;
}
};


class Solution {
public:
int maxProduct(vector<string>& words) {
int size=words.size();
int max=0;
vector<int> word(size,0);
for(int i=0;i<words.size();i++){
for(int j=0;j<words[i].size();j++)
word[i]|=1<<(words[i][j]-'a');
}
for(int i=0;i<words.size();i++){
for(int j=i+1;j<words.size();j++){
if((word[i]&word[j])==0&&words[i].size()*words[j].size()>max)
max=words[i].size()*words[j].size();
}
}
return max;
}
};


### 学籍管理系统文档

#### 北邮教务系统评教脚本

Published on September 17, 2017

#### 72.Edit distance

Published on September 17, 2017