字符串长度最大乘积

[编程题]字符串长度最大乘积

热度指数：7029 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

已知一个字符串数组words，要求寻找其中两个没有重复字符的字符串，使得这两个字符串的长度乘积最大，输出这个最大的乘积。如：

words=["abcd","wxyh","defgh"], 其中不包含重复字符的两个字符串是"abcd"和"wxyh"，则输出16

words=["a","aa","aaa","aaaa"], 找不到满足要求的两个字符串，则输出0

数据范围：输入的字符串长度满足 $2 \le n \le 100 \$ ，保证只包含小写字母

输入描述:

Input:

["a","ab","abc","cd","bcd","abcd"]

输出描述:

Output:

4

示例1

输入

["a","ab","abc","cd","bcd","abcd"]

输出

备注:

Input中，不包含相同字符的有三对：
"ab"和"cd"
"a"和"cd"
"a"和"bcd"
所以字符串长度乘积的最大值是4

算法知识视频讲解

Java

呃。。。

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        String sub = str.substring(1,str.length()-1);
        String[] strs  = sub.split(",");
        for (int i=0;i<strs.length;i++){
            if (strs[i].length() == 0)
                continue;
            strs[i] = strs[i].substring(1,strs[i].length()-1);
        }
        int max = 0;
        HashSet<Character> set = new HashSet<>();
        for (int i=0;i<strs.length;i++){
            for (int j=i+1;j<strs.length;j++){
                set.clear();
                int k;
                for (k=0;k<strs[i].length();k++){
                    set.add(strs[i].charAt(k));
                }
                for (k=0;k<strs[j].length();k++){
                    if (set.contains(strs[j].charAt(k)))
                        break;
                }
                if (k == strs[j].length()){
                    int length = strs[i].length()*strs[j].length();
                    if (length > max)
                        max = length;
                }
            }
        }
        System.out.println(max);
    }
}

发表于 2019-08-03 20:21:44 回复(0)