最大单词长度乘积

最大单词长度乘积

 


 

变量简洁正确完整思路
枚举两个单词,wordsi wordsj  如果没有重复单词就更新答案ans,判断重复用哈希集
seen遍历wordsi,然后遍历wordsj看是否存在
class Solution {
public:
    int maxProduct(vector<string>& words) {
        int ans=0,n=words.size();
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(isok(words[i],words[j])){
                    int len1=words[i].size(),len2=words[j].size();
                    ans=max(ans,len1*len2);
                }
            }
        }
        return ans;
    }
    bool isok(string&s1,string&s2){
        unordered_set<char>seen;
        for(auto c:s1)seen.insert(c);
        for(auto c:s2){
            if(seen.count(c))return false;
        }
        return true;
    }
};

变量简洁正确完整思路
哈希表用数组表示,26个,a对应0,z对应25
class Solution {
public:
    int maxProduct(vector<string>& words) {
        int ans=0,n=words.size();
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(isok(words[i],words[j])){
                    int len1=words[i].size(),len2=words[j].size();
                    ans=max(ans,len1*len2);
                }
            }
        }
        return ans;
    }
    bool isok(string&s1,string&s2){
        vector<int>seen(26,0);
        for(auto c:s1)seen[c-'a']=1;
        for(auto c:s2)if(seen[c-'a']==1)return false;
        return true;
    }
};

变量简洁正确完整思路
哈希表用seen二进制表示,a对应第0位,z对应第1位
class Solution {
public:
    int maxProduct(vector<string>& words) {
        int ans=0,n=words.size();
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if(isok(words[i],words[j])){
                    int len1=words[i].size(),len2=words[j].size();
                    ans=max(ans,len1*len2);
                }
            }
        }
        return ans;
    }
    bool isok(string&s1,string&s2){
        int seen1=0,seen2=0;
        for(auto c:s1){
            int bit=c-'a';
            seen1|=1<<bit;
        }
        for(auto c:s2){
            int bit=c-'a';
            seen2|=1<<bit;
        }
        return (seen1&seen2)==0;
    }
};

变量简洁正确完整思路
预处理每个字符串的二进制seen[n],ij用到就&一下
class Solution {
public:
    int maxProduct(vector<string>& words) {
        int ans=0,n=words.size();
        vector<int>seen(n,0);
        for(int i=0;i<n;i++){
            for(auto c:words[i]){
                seen[i]|=1<<(c-'a');
            }
        }
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                if((seen[i]&seen[j])==0){
                    int len1=words[i].size(),len2=words[j].size();
                    ans=max(ans,len1*len2);
                }
            }
        }
        return ans;
    }
};

 

上一篇:vue实现移入移出事件


下一篇:[leetcode] 1034. Coloring A Border