leetcode318. Maximum Product of Word Lengths

Moxmi 發布于2019-08-15 14:43 / 2599人閱讀

摘要：將低位的二進制數分別對應字母，從而用二進制數實現一個簡單的。因此單詞對應的二進制數為那么比較兩個單詞是否有重復的字母只需要將二者的二進制形式進行操作即可。

題目要求

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.

有一個字符串數組，從該字符串數組中找到兩個字符串，要求滿足這兩個字符串之間沒有相同的字母，同時它們的長度的乘積最大。

思路和代碼

這道題的重點在于如何優化字符串的比較。直觀的來說，我們無法避開復雜度為O(n^2)的循環因為必須進行兩兩比較才能識別出最大的乘積。但是我們可以優化字符串的比較。

既然只需要知道兩個字符串是否有相同的字母，那么我們可以采用一種數據結構將每個單詞所有的字母記錄下來。這里采用的是二進制數的形式。我們知道字母的數量不會超過26個，因此我們使用32位的整數來存儲。將低26位的二進制數分別對應字母a-z，從而用二進制數實現一個簡單的map。

因此單詞ae對應的二進制數為00000000 00000000 00000000 00010001

那么比較兩個單詞是否有重復的字母只需要將二者的二進制形式進行&操作即可。如果沒有重復字母，則結果應該為0.

public int maxProduct(String[] words) {
        int length = words.length;
        int[] wordToInt = new int[length];
        for(int i = 0 ; i

想要了解更多開發技術，面試教程以及互聯網公司內推，歡迎關注我的微信公眾號！將會不定期的發放福利哦~

GPU云服務器云服務器 Lengths Maximum Leetcod Product

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/68775.html

Maximum Product of Word Lengths

摘要：題目鏈接除了用先處理之外，還可以用保存所有不含某個字母的，這么寫。 Maximum Product of Word Lengths 題目鏈接：https://leetcode.com/problems... public class Solution { public int maxProduct(String[] words) { // bit array t...

妤鋒シ 2019-08-14 17:24 評論0 收藏0
leetcode 部分解答索引（持續更新～）

摘要：前言從開始寫相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新更新前言從開始寫leetcode相關的博客到現在也蠻多篇了。而且當時也沒有按順序寫～現在翻起來覺得蠻亂的。可能大家看著也非常不方便。所以在這里做個索引嘻嘻。順序整理 1~50 1...

leo108 2019-08-15 14:26 評論0 收藏0
[LeetCode] 628. Maximum Product of Three Numbers

Problem Given an integer array, find three numbers whose product is maximum and output the maximum product. Example 1:Input: [1,2,3]Output: 6Example 2:Input: [1,2,3,4]Output: 24Note:The length of the ...

jindong 2019-08-16 13:39 評論0 收藏0
leetcode 628 Maximum Product of Three Numbers

摘要：題目詳情輸入一個大小大于等于三的數組，給出其中任意三個數乘積中的最大乘積想法這道題最主要的是要考慮正負數的情況。如果全都是正數相乘比較大，就取三個最大值相乘即可。題目詳情 Given an integer array, find three numbers whose product is maximum and output the maximum product.輸入一個大小大于...

CoreDump 2019-08-15 13:57 評論0 收藏0
前端 | 每天一個 LeetCode

摘要：在線網站地址我的微信公眾號完整題目列表從年月日起，每天更新一題，順序從易到難，目前已更新個題。這是項目地址歡迎一起交流學習。這篇文章記錄我練習的 LeetCode 題目，語言 JavaScript。在線網站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公眾號： showImg(htt...

張漢慶 2019-08-23 13:42 評論0 收藏0