单词长度最大乘积

• 前言
• 一、单词长度最大积
• 二、题解
• 总结
• 参考文献

前言

单词长度最大乘积，如何获得无重复字母的单词最大乘积。如何拆解问题？如何举一反三？

一、单词长度最大积

给定一个字符串数组 words，请计算当两个字符串 words[i] 和 words[j] 不包含相同字符时，它们长度的乘积的最大值。假设字符串中只包含英语的小写字母。如果没有不包含相同字符的一对字符串，返回 0。

二、题解

如何拆解问题？
1）如何快速判断两个单词间是否有重复字母？
2）在字母非重复的基础上，如何得到两个单词长度乘积最大？
->通过标记数组来判断两个字符串是否有重复字母。
->通过两层遍历+改变边界来快速获取乘积最大值。

package com.xhu.offer.offerII;

import java.util.Arrays;

//单词长度的最大乘积
public class MaxProduct {
    //总结：思维一直稳定的向前走，实在走不动就看题解，而不是浪费时间（短短续续不看题解或非短短续续就是不看题解）。
    //总结：多观察题目已知条件，这大可能是减少时空甚至是解题的关键。
    public int maxProduct(String[] words) {
        //先排序，然后开始双指针遍历，一旦得到一个乘积，则返回结果。
        Arrays.sort(words, ((o1, o2) -> {
            return o2.length() - o1.length();
        }));

        int res = 0;
        int bound = words.length;
        for (int i = 0; i < bound; i++) {

            int[] mark = new int[26];
            for (int k = 0; k < words[i].length(); k++) mark[words[i].charAt(k) - 'a'] = 1;

            for (int j = i + 1; j < bound; j++) {
                boolean flag = true;
                for (int m = 0; m < words[j].length(); m++)
                    if (mark[words[j].charAt(m) - 'a'] == 1) {
                        flag = false;
                        break;
                    }
                if (flag) {
                    int temp = words[i].length() * words[j].length();
                    res = res < temp ? temp : res;
                    bound = j;
                    break;
                }
            }
        }
        return res;
    }



}

总结

1）思维一直稳定的向前走，实在走不动就看题解，而不是浪费时间（短短续续不看题解或非短短续续就是不看题解）。
2）多观察题目已知条件，这大可能是减少时空甚至是解题的关键。

参考文献

[1] LeetCode 原题