本文主要是介绍用枚举算法解决Leetcode第318题最大单词长度乘积问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
318. 最大单词长度乘积
难度：中等
问题描述：
给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。
示例 1：
输入：words = ["abcw","baz","foo","bar","xtfn","abcdef"]
输出：16
解释：这两个单词为 "abcw", "xtfn"。
示例 2：
输入：words = ["a","ab","abc","d","cd","bcd","abcd"]
输出：4
解释：这两个单词为 "ab", "cd"。
示例 3：
输入：words = ["a","aa","aaa","aaaa"]
输出：0
解释：不存在这样的两个单词。
提示：
2 <= words.length <= 1000
1 <= words[i].length <= 1000
words[i] 仅包含小写字母
这个问题可以借助枚举算法来解决
枚举算法的基本思想是列举出问题所有可能的解，然后检验每一个列举是否为问题真正的解。它涉及到三个重要步骤：确定研究范围、列举和检验。
具体到本题中
研究范围：words数组中所有的单词构成的两两组合
列举：利用二重循环遍历出words中不同的单词组合
检验：对取出的两个单词判断是否有公共字符，如果没有，再检验字符长度的乘积是否最大
实现依据：
1、求两个单词长度的乘积，如果两个单词分别为word1和word2，则长度的乘积k=len(word1)*len(word2)
2、如何判断两个单词没有公共字母？对于两个单词word1和word2，先将其转换为集合分别去掉重复字符，然后观察集合的长度之和与它们并集的长度是否相等，如果相等，说明没有公共字符，否则有。
程序如下：
#检查是否有公共字符，如果有返回True，否则返回False
def checkshare(word1,word2):word1=set(word1)word2=set(word2)word=word1|word2if len(word)==len(word1)+len(word2):return Falseelse:return True#利用二重循环枚举，返回满足条件的最大单词长度乘积
def maxproduct(words):n=len(words)maxlen=0for i in range(n-1):for j in range(i+1,n):k=len(words[i])*len(words[j])if (not checkshare(words[i],words[j])) and k>maxlen:maxlen=kreturn maxlen#输入
words=eval(input('pls input words='))#输出
print(maxproduct(words))运行实例一
pls input words=['abc','def','cdefgh','ijklmn']
36
运行实例二
pls input words=['ab','ac','cd','defgh']
10
感悟：长城不是一天修成的，不必太在意题的难易，只要脚踏实地，认认真真解决好每一道题，必然有所收获。
这篇关于用枚举算法解决Leetcode第318题最大单词长度乘积问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
