leetcode 318. Maximum Product of Word Lengths(python)
持續創作,加速成長!這是我參與「掘金日新計劃 · 6 月更文挑戰」的第11天,點選檢視活動詳情
描述
Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.
Example 1:
Input: words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output: 16
Explanation: The two words can be "abcw", "xtfn".
Example 2:
Input: words = ["a","ab","abc","d","cd","bcd","abcd"]
Output: 4
Explanation: The two words can be "ab", "cd".
Example 3:
Input: words = ["a","aa","aaa","aaaa"]
Output: 0
Explanation: No such pair of words.
Note:
2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] consists only of lowercase English letters.
解析
根據題意,給定一個字串陣列 words,返回 length(word[i]) * length(word[j]) 的最大值,其中兩個單詞不能有相同的字母。 如果不存在這樣的兩個詞,則返回 0 。
如果按照常規的思路,我們兩兩進行比對,而假如兩個字串的長度為 L1 和 L2 ,要達到兩個字串中沒有相同的字母,那麼我們的時間複雜度為 O(N^2 * (L1 * L2)) ,這肯定是超時的,我們要保證時間複雜度能夠在 O(N^2) 之內,我們肯定要降低兩個字串的比對效能 O(L1 * L2) 為 O(1) ,根據最近“每日一題”都在考位運算我們就能猜到,這道題也是在考察位運算,我們使用位運算結果來表示字串,一共 26 個字母對應 26 個二進位制位,我們只需要將每個單詞表示成二進位制即可,這樣我們在比對兩個字串所代表的二進位制是隻要判斷 mask[i] & mask[j] 等於 0 即可表示兩個字串沒有相同的字元存在,時間複雜度可以降到 O(1) 。
整體的時間複雜度為 O(N^2) ,空間複雜度為 O(N) 。
解答
class Solution(object):
def maxProduct(self, words):
"""
:type words: List[str]
:rtype: int
"""
N = len(words)
result = 0
mask = [0] * N
for i,word in enumerate(words):
for j in range(len(word)):
mask[i] |= 1 << (ord(word[j]) - ord('a'))
for i in range(N):
for j in range(i + 1, N):
a = words[i]
b = words[j]
if not mask[i] & mask[j]:
result = max(result, len(a) * len(b))
return result
執行結果
Runtime: 499 ms, faster than 67.32% of Python online submissions for Maximum Product of Word Lengths.
Memory Usage: 14.2 MB, less than 69.91% of Python online submissions for Maximum Product of Word Lengths.
原題連結
http://leetcode.com/problems/maximum-product-of-word-lengths/
您的支援是我最大的動力
- linux 安裝 ES 8.0 和 kibana 8.0 爬米共坑
- ES 8.0 及其生態配置過程一條龍服務
- 2022 年中紀
- leetcode 1048. Longest String Chain(python)
- leetcode 1354. Construct Target Array With Multiple Sums(python)
- leetcode 2311. Longest Binary Subsequence Less Than or Equal to K(python)
- leetcode 2304. Minimum Path Cost in a Grid(python)
- leetcode 2303. Calculate Amount Paid in Taxes(python)
- 帶你輕鬆入門 Bert
- leetcode 1332. Remove Palindromic Subsequences(python)
- leetcode 3. Longest Substring Without Repeating Characters (python)
- leetcode 2296. Design a Text Editor (python)
- leetcode 2293. Min Max Game(python)
- leetcode 1584. Min Cost to Connect All Points(python)
- leetcode 318. Maximum Product of Word Lengths(python)
- 沙灘 美女才是夏天的正確開啟方式
- leetcode 2275. Largest Combination With Bitwise AND Greater Than Zero (python)
- leetcode 2258. Escape the Spreading Fire(python)
- leetcode 2257. Count Unguarded Cells in the Grid(python)
- leetcode 2273. Find Resultant Array After Removing Anagrams(python)