Leetcode 318 Maximum Product of Word Lengths 字符串处理+位运算

先介绍下本题的题意:

在一个字符串组成的数组words中,找出max{Length(words[i]) * Length(words[j]) },其中words[i]和words[j]中没有相同的字母,在这里字符串由小写字母a-z组成的。

对于这道题目我们统计下words[i]的小写字母a-z是否存在,然后枚举words[i]和words[j],找出max{Length(words[i]) * Length(words[j]) }。

小写字母a-z是26位,一般统计是否存在我们要申请一个bool flg[26]这样的数组,但是我们在这里用int代替,int是32位可以替代flg数组,用 与(&),或(1),以及向左移位(<<)就能完成。如“abcd” 的int值为 0000 0000 0000 0000 0000 0000 0000 1111,“wxyz” 的int值为 1111 0000 0000 0000 0000 0000 0000 0000,这样两个进行与(&)得到0, 如果有相同的字母则不是0。

 class Solution {
public:
int maxProduct(std::vector<std::string>& words)
{
std::vector<int> flg_;
for (std::vector<std::string>::size_type i = ; i < words.size(); ++i){
int tflg_ = ;
for (std::string::size_type j = ; j < words[i].size(); ++j){
tflg_ |= ( << (words[i][j] - 'a')); // 对于'a' 就是 1 而对于‘b’是 10 'c'是100
}
flg_.push_back(tflg_);
}
int ans = ;
for (std::vector<int>::size_type i = ; i < flg_.size(); ++i){
for (std::vector<int>::size_type j = i + ; j < flg_.size(); ++j){
if ((flg_[i] & flg_[j]) == ) ans = std::max(ans, (int)(words[i].size() * words[j].size()));//words[i]和words[j]中没有相同的字母
}
}
return ans;
}
};
上一篇:我的GTD中收集的书单


下一篇:猫眼电影爬取(一):requests+正则,并将数据存储到mysql数据库