华为OD机考算法题：计算最大乘积

题目部分

题目	计算最大乘积
难度	易
题目说明	给定一个元素类型为小写字符串的数组，请计算两个没有相同字符的元素长度乘积的最大值。 如果没有符合条件的两个元素，返回 0。
输入描述	输入为一个半角逗号分隔的小写字符串的数组，2<= 数组长度<=100，0< 字符串长度<= 50。
输出描述	两个没有相同字符的元素长度乘积的最大值。
补充说明	无
------------------------------------------------------
示例
示例1
输入	iwdvpbn,hk,iuop,iikd,kadgpf
输出	14
说明	数组中有 5 个元素。 iwdvpbn 与 hk 无相同的字符，满足条件，iwdvpbn 长度为 7，hk 长度为 2，乘积为 14 （7 * 2）。 iwdvpbn 与 iuop、iikd、kadgpf 都有相同的字符，不满足条件。 iuop 与 iikd、kadgpf 均有相同的字符，不满足条件。 iikd 与 kadgpf 有相同的字符，不满足条件。 因此，输出为 14。

---

解读与分析

题目解读：

给定一个长字符串，以 “,” 为间隔符分隔成多个字符串。请从这些字符串中找出两个字符串，保证在这两个字符串中不存在相同字符的前提下，使两个字符串的长度的乘积最大。

分析与思路：

此题的步骤可以分为解析字符串，排序、数据初始化、遍历，详细说明如下：
1. 解析字符串。对输入的字符串以 “,” 为间隔符，把它们解析成多个字符串，放到数组 stringArr 中。
2. 对数组 stringArr 排序。排序规则为长度最长的字符串排在最前面。
3. 数据初始化。对已排序的 stringArr，统计每个元素（字符串）所包含的字符，放到集合中；计算字符串的长度。创建两个数组，第一个数组为 charSetArr，其第 i 个元素为 stringArr 中第 i 个元素包含的字符结合；第二个数组 lengArr，其第 i 个元素为 stringArr 中第 i 个元素的长度。
4. 遍历。
1)  初始化乘积，设为 maxProduct，初始值 0。
2)  两两比较字符串。把字符串 stringArr[0] 分别与 stringArr[1]、stringArr[2] …… stringArr[n -1] 进行比较；之后把字符串 stringArr[1] 分别与 stringArr[2]、stringArr[3] …… stringArr[n -1] 比较。
比较规则是，在比较时，如果不存在交集，即charSetArr[0] 与 charSetArr[i] 不存在交集，则计算 lengthArr[0] 与 lengthArr[i] 的乘积，设为 tmpProduct，如果 tmpProduct 大于 maxProduct，则把 tmpProduct 赋值个 maxProduct。当找到 charSetArr[0] 与 charSetArr[i] 不存在交集后，不再判断 charSetArr[0] 与  其他字符串是否存在交集，因为已经不存在乘积比它更大。

此方法的时间复杂度为 O()，空间复杂度为O()。

---

代码实现

Java代码

import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;/*** 计算最大乘积* * @version 0.1* @author Frank**/
public class StringLengthMaxProduct {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNext()) {String input = sc.nextLine();processStringLengthMaxProduct( input );}}private static void processStringLengthMaxProduct( String input ){String[] strArr = input.split( "," );Arrays.sort( strArr, new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {// 长度最长的排在最前面return o2.length() - o1.length();}});Set[] charSetArr = new HashSet[ strArr.length ];int[] lengthArr = new int[ strArr.length ];initCharSetInfo( strArr, charSetArr, lengthArr );int ret = getMaxProduct( charSetArr, lengthArr );System.out.println( ret );}private static void initCharSetInfo( String[] strArr, Set[] charSetArr,int[] lengthArr ){for( int i = 0; i < strArr.length; i ++ ){String curStr = strArr[i];lengthArr[i] = curStr.length();Set<Character> curSet = new HashSet<Character>();for( int j = 0; j < curStr.length(); j ++ ){curSet.add( curStr.charAt( j ) );}charSetArr[i] = curSet;}}private static int getMaxProduct( Set[] charSetArr,int[] lengthArr ){int maxProduct = 0;int size = charSetArr.length;boolean needBreak = false;for( int i = 0; i < size; i ++ ){for( int j = i + 1; j < size; j ++ ){if( ( j == i + 1 ) && ( lengthArr[i] * lengthArr[j] < maxProduct ) ){needBreak = true;break;}// 包含相同字符if( !Collections.disjoint( charSetArr[i], charSetArr[j])){continue;}int product = lengthArr[i] * lengthArr[j];if( product > maxProduct){maxProduct = product;}break;}if( needBreak ){break;}}return maxProduct;}
}

JavaScript代码

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;
void async function() {while (line = await readline()) {processStringLengthMaxProduct(line);}
}();function processStringLengthMaxProduct(input) {var strArr = input.split(",");strArr.sort(function(a, b) {return b.length - a.length;});var charSetArr = new Array();var lengthArr = new Array();initCharSetInfo(strArr, charSetArr, lengthArr);var ret = getMaxProduct(charSetArr, lengthArr);console.log(ret);
}function initCharSetInfo(strArr, charSetArr, lengthArr) {for (var i = 0; i < strArr.length; i++) {var curStr = strArr[i];lengthArr[i] = curStr.length;var curSet = new Set();for (var j = 0; j < curStr.length; j++) {curSet.add(curStr.charAt(j));}charSetArr[i] = curSet;}
}function getMaxProduct(charSetArr, lengthArr) {var maxProduct = 0;var size = charSetArr.length;var needBreak = false;for (var i = 0; i < size; i++) {for (var j = i + 1; j < size; j++) {if ((j == i + 1) && (lengthArr[i] * lengthArr[j] < maxProduct)) {needBreak = true;break;}// 包含相同字符if (!isSetDisjoint(charSetArr[i], charSetArr[j])) {continue;}var product = lengthArr[i] * lengthArr[j];if (product > maxProduct) {maxProduct = product;}break;}if (needBreak) {break;}}return maxProduct;
}function isSetDisjoint(charSet1, charSet2) {for (var ele of charSet2) {if (charSet1.has(ele)) {return false;}}return true;
}

(完)