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

题目部分

解读与分析

题目解读：

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

分析与思路：

此题的步骤可以分为解析字符串，排序、数据初始化、遍历，详细说明如下：
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>() {
	    @Override
	    public 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;
}

(完)