Leetcode 318答案详解（基于C++位操作）_irbctob

随机Pick到Leetcode的318题，选择了C++基于STL的答题模式。
先看题目，

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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

中文意思就是，算了，既然做到这个题，这题的意思大家应该非常明确了，就不献丑翻译，还是老老实实解题。

简单说来，就是一个字符串数组里面，找到两个不含相同字符的字符串，求出它们的乘积之和。

开始看到以为这么简单的遍历题目，直接循环不就可以了么？

在数组里，每一个元素字符串依次和其他的字符串比较，看是不是有字符是共同的，没有则计算两个字符串的长度之和。

我写的代码如下：

class Solution {
public:
    int maxProduct(vector<string>& words) {
        int maxNum = 0;//两层for循环依次比较字符串,剔除自身与自身的比较
        for(auto i = words.begin();i != words.end()&& i != j; i++)
        {
            for(auto j = words.begin();j != words.end(); j++)
            {
                int count = compare(*i,*j);
                if(maxNum < count)
                {
                    maxNum = count;
                }
            }
        }
        return maxNum;
    }

    int compare(string line1,string line2)//比较两个有没有共同的字符，没有则计算长度积
    {
        int flag = 1;
        int count = 0;
        for(auto val:line1)
        {
            if(line2.find(val) != line2.npos)
            {
                flag = 0;
            }
        }
        if(flag)
        {
            count = line1.size() * line2.size();
        }
        return count;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

自定义的测试用例：

[“abcw”,”xyz”,”defg”]
结果是：
16

所以小数据可行。

但是：
提交以后，得到的是时间超时，然后我看到给出的测试用例是：

["rcpzismixnpnmbqeitlwptppjpidjblkppuzpmwibjoptzmobhydloxqexe","yqpqpll","blwjfpljvdeeuafqscxdgwybowchnbmkgoyofvrrpww","mwsedjtqtpbygheohbrbntvlsmpixwu","ftobpfdgcqtoopikksuxaeimchhdbxwwyeymjihtncyuvcqguchlgmdbshwqupfkabsgaeqntvrrlyymglatlfsuajzklg","tdwhzbeyxrbxfhxebaaookkryzmsetwuecejmvcthbbajnmcmdpihdmpjmrdyro","sjepkrcpfruskqj","zljiwtwhtditxtcimquasaugyfqfukgruvgarw","bvcnxkskhkwoosoueooyxafvjgueovzbjofqthgpiapgvtulqltfars","qiekuqtlnuguzruxxpmtssofgw","qrjukbljcoibxwwkzgpmzmphimzlmmlxuzlelwavfdzqpbnugdmljehutdfbgzojkqunjhuurmpthogqsni","ebnxwmxfhtgwjypkivuozrulqmltueadnnleubbpeevhdtbgwbyhaykwi","igbkj","kadrv","aspohodbstdbktiddqwnfneyvsufdhopdaqztkkuqtkjlymybwjdnjdbrlabwmchigztvpwtihhqnhnbcuqrusdeiruyjbhea","mfputfnzupzvkbgakgubvxazadcmk","oojnpjqguowqrgesxztkecfsaybglnezwshvkdtemomhnnxpvlalyeoyfxuzodowpwgliklflugfsmixkz","wszoydrrfhyliadcehappdkdgaobspkkukzyqlppz","zoahfbzunrgzdvcpbedqplvhkkiuwurgjoatfbmnnubkaaybwsybejfqmsfsnzjvyruvlzuoavufotlezyubtkbqjbuki","eessjisltiydyn","edhoqqnxwtbpxftiiqdfkimvptzpdsujwepzzyghvgkixlqpqxnvfc","vnfvlcebiupaqqykslkadnphgwgiiuplczzhfllpudkkfklxnpljuffobuwwyjzbfiyrbczaqiflqgctgwefeydd","xljxcdvjqtvewozxtdljlhbnomxrmojplttjffwzlbaakijyjfbnjvdbofflepauegnlsuhcnvyuabmtwftolukxfhpzmisxufk","qnkpiitkzbdtydxberoyvphzbsgxvdkevulfziutxxnqtooofbcknhhbmzffrkluqwjxalcccuejwisdzizw","mkbncuqwqloonxyprilzfdytsxracpfyogmpgabnwqpiamruurfjuhqjymovqvgvxzvjjtlwxprnszdpcuvm","synemltbynpusymlyzbdptjhqrybolqbfbunmzfxnyuzwttrarbkzxtfymfsqxnszvnyy","ibcobpho","otehstxibmordymcpcqcpzegwcwwnknlwvihufhrcqqgiwnyrzhqesleiwdvmmjdsfewr","hhgxeykeulu","dzgtl","bwomxslyqdqovmjnyar","dmhznzcrzzwiajmqzcztdfvvkt","xinvkvvuikyyknlggoocroweikvlwhpdytbblffujqgsvbwpnxvmsqmvydsidwudpcjyzgufjbbvwkslsatcuzhczrljyzinsnd","ebjsyceudmrpqfllyrvehetudldqdlwlglenoistevzfwndrxcypeoqlohzodmnjw","kbgnurhgrefhmjhcdnerdedtpcwqgamqfqgkwsbausmjrfvmasgxxncrmmvwsfxdto","djlik","cmraajghuiuzrcifppjyrpvrlyiacobgojimkjastjvji","patyuyhwzjjlofiryaskleoxxevkzvmjspp","pduphfipwjehvefaybjkukyunrocvycosawgfdyfrfpoqitduqmczhyexrzjnyolkeyfcjtgxayexurwjzsfkrfonomymyduuuy","nebbgqcyiubtiecvxxjlrplvkntltmjrgjyppw","abcnycubqbgikqohyehillavktlylrltgolnzxswffeymjozhbaugihrvrmcxptubqtzegxuovrhqzlexlorjnky","yqaappoavhamh","sghmcypeuticifscriwnnpneihxfopuxlqsizfjqpngimfkgsacjjscssdzjyedgxzeihrhaseguriqchsbohkvyvqemmsogbkjxb","tlejxnisuqbttmztcbxpcukwbshvnezqkzogphkktbfvagdfrfpkjxhlvbspmysrfuhykkhvvxjtfyzxfrzslzzjvieeithuzh","qbtmwxudxekggjyoelvbbnzsajjuvuteorwrsugoxwjdgdqxeizcijrhtbjzlsddemtstekdeylczoepcytwnxtiji","qbaybychlynfhmnklbhzylbmwtjxgfusnjfcpibsiqisgoyhfvgbgswwxwvsyjhimqkuhfwqrewnrjkypuvlubltptgaxfi","xtfnuba","exbvewextuxozrcoshx","sfjejpgdmehdpbixasdftnnnnzhpglwrmsuzddolcgdvcvnnpvqozvdgczoezsplmeoslgswgghkbixwqcdw","pmcjitkgxiebhktmhmelkxusdlbkrpyemdirmtlulvberuosyemshb","lxvqwkaaqkiapqirtqqiiooogwdvywrxgvkejdogmthpvzismoepzinayeqxcultuwggwhkufsnymob","wnprabtuz","apnerrtiviaerjnrjrgzqkfsglcigwrdvioidjowaxobfxorfpghatidatshzgmbfwufxsbpicpbm","mrwxawbhzbrakgvisxzecjvszniqkznlbrwznguaangbnsmtltgnoubrivcdqyuwlgvekffevohghpitlfkbeazt","qgcvctdujljedeiqfvodceecsxvvuyzzffyoyxtebwtmrqqdtjgkuulgctyb","upgvcxbitszluutddinydptdnihksmupzlstiizubyjyrbidqjzdtwnnvq","mgeoccocmhpixhmchnren","tmn","pvrefvkyjukwmbazxxbyonsoawdeovivcsfxvhchyiqdfdixtolmky","lurmbfodccsxyhqvnukgpwwlrmvgxmiscwysmersiyelysqhepjnsuumonnouzzuacttqxgpnpizklunclyzzwmsholzseabokvj","fxfggprqnechxyurodpeywghuhts","qkvyrbozdrstnvzcypuhlqghpvnppiamvcfykvtvpwmmaejlduodhuhexktdfjhnauppdxhqlqxyjqvvqcybpyyafrfujtuj","cclifhvkzgpcacaiofhvtsfvmoztyk","wythiwcfcmjirbfuqpzbxplcxxczxmrtvizobbymgiwfqgucceigubvsghrxvxvdowvezmkqhneffsmqpfawagdwfaunvq","wqlkrqpltsafqauumdlujmvagfuarfwodgpnnkrbpidta","ocozunfavuvwnvdirarfghetkktgzniudgdtyvfwkmmlvztfvdfowabbsxcdmmmamzqwzy","etghnxbuqahrcbxdemdfqjwghhkihdnhdpdvnnhkazojm","opkkiesfdecvjbdjruhvq","mhylzjwzpxnryntqlouidyoogxuwhcxrjrymymmukhvfbhweg","ftlqmccjmlralysphx","ceqrnlnbdyrvg","qaxyjwbnejqaxbnujlshftutyxmwjnpbrwnaybxariyojvyhociccqxpzueqmgbisxpnyakigukcursnw","jhwdqytaqfsxhnrcdibgghuosngtbhujibyqkwquinyhrvajavgfbxnossjnnf","rjdxupzseuiqfqnuhdgihvevdvjuekxoyptbgnyzakhupowhkdkavujqhjwjzltsonbdjvkkgcdrfcjpntcebidpwpeclcya","kmuuzprkdcuyjolcnquekengqikqrlpbx","soozogfbvznupuareaulxztnmjgwumjamadsuyvznzwaupbyzkmutlppfpjlygttqlphzckufzrnatnxrypdwewgdzuuxav","nutfbidlofigdwdoovojdmllhvqsnmmxsohyyopgbnhkojwmvxvsyzzsoexsovpsxwmqdoshsyqqmgmktyn","twwocmdypvqqueikcctguvttuqi","tzswmqnmsiprtxyvzpphlgpztbgyvv","tbxozpnqwplsvftrecfdbzjkawytfoqnoazqppkszmcsghmwglbvskxtwynttmjmxjaqrxthffwqtzdjbsppytrcqlxcexotu","cdjxtvhylwsfkmnzckcc","syibmotvwsax","ljuhkatlkohssahbfrarualsmlogwkkbqzjvsxbrbeobuexjzumywyrlajvkitqughwqfxxtdn","ptzhnijzoekupfeeqbtekqsnwkozutiypuvcttnndwnwlmsrx","bqlwywvioiswxxugrjmvpgqdutpppqschrzoz","ttzqjmaxkosdqsviwedpqocmaycfyvisjqzqfvuztruxxkzdsthosxnsibtzmnybz","flgsnbkwaevtprbcfnyjaghncvdrgcodsqzpdcpgjbtejellvgjmzrojdiyewfzbrpkufqytsdhsybbiedjlwvbwmdbexdr","fodsxqousjrtgtqrjnuvknxvljavaoukkqkwluvcnvhpyknpoinrovvqsdbnlbtgyesgrhyzpqfjexfagrvakqoftaizy","fzzhlkqbnttownekptgkwlagfbkfquncpafgbhwgfogjapheqxgafqufordltuupmujgkwloparurkefqsffqjwnuhexrhyqjk","goxitvlxlxtmooxqkmnhosnmbmrryxooaywhbmqemecmltdaabppopqauqpidimkmpromjlhssdzexka","wtejkrwejypipxmdpzcupxfu","xclboktsndzjynksqoynujdtvvhdpabmveeogga","naszwbuly","zaiejajlhmrgczpkptavgpeyczqjpiovtzbevezpexguairwwjziudvlouqublghainqksjrec","gokimdzwurxifipsffqrigpfwkakhiirywsoksivrklxtzcrobqdkubvguzllqefkasdqbyxgyhxwrwyyutpkpbezxaymlyuarts","qssmflylfgdyxznbvxraumrrgjmonvhyqvlvafctxxtwvqpbpfacojlnvhkwohmfxyji","xlliikrpowqbnsmwilebfduprffgegwritmhjniqyxycm","yvvxwzbiioagyepagmoocszzfvmkvibepoezlnf","ictvrxcgkfjmzlhelselo","iuykhxaxauegav","aghzxkmukcrrjwtdqxpjvmqqbusyjnopionozrtrjrgnricgwehoueby","ttnidsvfdxdwpslyldwkpncuulqpvkrfcuccgwocxoelsuavtnbcfqjiqurfltejsmtifuswpggzloukdhfcuvyomon","mficnfzlyosgoddbfssfcrogubpaiawfejilpuqwbiildujckiynvu","znryadyyiupboxrleeectdygdbzuzgphcftiidtfkwlrqbbtgimrynzkhra","fsosoklgmzellytyihcrbqcvspivbcjmgpqjwfmfkkvqigejwoteqaeyqcdtmecxmdxxjscwecfyiinkzincbykq","zpqmewaxjxagxxcluqxumooxocppiioxqtlkuvxfaobarcwlhqbzrxxiytmxgguzxlqkztmzwqnsowwnqabkrvnijgwitjuhzetwf","fhazavkdo","mxvowyrvgduijrbuuobraeggfspwdxpsoaxfuoetrbbawaxulfzliciumsxodlasozceldtibvdgoxxu","kpkidvpyeuugtpjjcbnaljyrczrtbzoak","joorvimvcwjxtjcazfgbncipmmcfmrrzhzbfweyrpigpia","ymwmcblzsupubscwldapbdxxptypcosdsbbjowvytuycxkbmdmwkicyjpxgqwhavfi","dpchicrvcmijlbhdwsaasdzq","xtdocyyicdpqnkcomytytxesdxqslmwpfecrjhbmoikeclipwazxgujvtdzqctzopsggywnidrrsjzreijbmtnkzmdzuofv","hxwgsiamwnrnnezhmbzllmdgvbzebpqxzsdkamoqovwqfzymnnjmfisbpiwgouclkvbyhlwjuzvnqnmabxxplvmkifaxexpsynb","eiswqugwladhgfaftmtdksvaglgjfgubpkphkdxaqze","sqodqlfndfoutdbjrlnbpswgiyyedabficgxozahtqpjfczvtqbcpbmrvtqq","xkyaqllzgwprlbbhxhsoniefzizrkxjrtzsezohfvgffutierkqbexrmuivctmwytaolfyzlvqmynxwupqic","dqfffpxutplmywhcedqneyiqaddvayrn","mwitvujsenjhcyeaevyadbvmywsqcgqefzhaqvryscxrznntlgnykmejfbjdpgrrkzkjjpjvewt","rkhegmfyybbzjafaqmtajmstwwvokiwyxlqrbavaxqnohpsrxbyobolyfwkdtfpzpvgm","sgpbrirbdjduldgvpxfsypwwakqhgryttcbnahehpafacw","nhxsqkynbbylmyofkeyussmaauofpuvmehesuogheppoyvcagoyrogumnqyvhvolgvtlmcjsgpeu","qderldyzgnzxatmzicfdrdwetbpshvkbdcjqthnmersy","gzoanfmupgvnyneivuzcruccbojsizkqjkixosczgxjicrddqpamesfygnkywtmrauprmqkwgtqrpttxfdqxticuvqalrfxou","quxmgivfjmrywyucy","ffefctbfvyldxiboaogkolxfuokkgdojkcftjpleohksp","usymxbxlejyniqmoxntsvxnsmnoyyavpoavasrszcyxbbwvoelifppbwkklarqfvcgryktupwirogooqeafaz","abpmlinmmfshsjbcxjlgijiokfcgkmgvthobmrxjylydqfhsotlaek","tawzbxnzfalhzfwutxo","eddncusyeumqegbrrpoapnramazebiozdngfvaavaysrgfbelsvwpbpneyndcjpjahp","vrrilfvhzxqfozjlvdjzqd","lpkvazgptlsjtmpfpepcnhqugsefbrkkqjgisnsaggmcfcdtrelpwifsgwkafpxtusgklmcrcwgjjhnznncsqzxsjrsmyiuasop","noyxvmpsbofpkienpcecrphnacnuwykyriyhwjahdehblounaoxjxjuxvxhfllpbz","vwwuiyrhlinwobcsndqknkgqvtomrc","ixyrneqglfcwkdorfewmtzvqhuinweyobhwjzbxdfpwem","prhvncykixvbuzlnszbprpvfkgktimseybmpor","nhxqsufcqcvinyutjkludinfewsqiidmxy","krclggfrivcucbhjvttfprpqdovkecn","eudpjfvrwddqditwzvfyqexnmbatzuunicigomepkjygycnywuxgjomrndunugjouctnqlvrarihasxtuctlzutxozl","jirvqmdedrwtdfyeofnrpeizjiyeiwyzpkwakz","xsnxopovpcslqsmpvfzjguqwcxxgtndojscugmeovlybrzbodkrkhswgmjnksykefvhfmpuuguyokvhykrhtjhdlwu","sgzznrcfosgyjofzotwoopmtdfohn","xjiiewzqwbtudpycviuewilegsuoehndeyaohkwdpcvjbvgtpivkxnesaeqeblvnqumkqxymqncvgtdubqmqnl","gxgturrjemcypgbqfqxspiaohgpukqc","unurckzehdrwmfmhhjhxwrkeirjbnkuigcjmwmjbfperfbefnsbktmuqqdxsfoxarhgejaaumpk","qffupuibdhdrcdfbqjnpobikrtwodqounzgmkdgwdspgxhiihvovhpeyztwcpupwhebkt","qbpuauhzkkocmbamnimqffqcmbfejhkiichvfzaskrwfvdgsezbgfqjpyobfetpyvk","cpmvpjygnasukvyxrvgurqxhfsyhhiblzycqvaysovzrrttrevhtllm","yajndsivogmufxhobrxprgbndbuuartvtkgviyvlfvfqpqjonqlaznshwxwdizmovrrezvwcmihubgztblppmurnya","sifcdsitxbmxskjxnymtfxguxmuihvkzodihiqroaparzepwvlqjylhzckvqpakvueshwzlfbk","pieqnpvczmlmemzmmrdatnpasulp","vmxhbznnynzvdipmxtxgdchqhtdyinhabpgbwyawolobdsafvj","esnvpykucurnkjubfbqhnpmahxrrkcadldsgdinmmioyicdzjulcdmbhyryszvxot","aucgxiwbixfyigirxnrmcgsfddgxmlzzgvhnoly","vkjpnpoxwwyrajbkooidqdpmsvluywozqtybrwdufv","sspkggztpibtmishfrwutnskctylkiycnwgvlxnmjisdmqeaiz","xu","grkklnrdljbjhezvwfhhvweobsnqfpybreqonrehochgrrenzlqlmlgnps","ekgksoznsnowsnif","nsshmhfxuqhlgcznmimmxxslbdbgzfwrszbbghngzvwvfsdbdjhuxxdplzqoo","cdte",
1