— LeetCode318. Maximum word length product

This is the 26th day of my participation in the August Text Challenge.More challenges in August

The title

Difficulty: Medium

Given a string array of words, find the maximum length(word[I]) * length(word[j]) that contains no common letters. You can think of each word as containing only lowercase letters. If no such two words exist, return 0.

Example 1:

Input: [abcw ", "" baz", "foo", "bar", "XTFN", "abcdef"] output: 16 explanation: the two words "abcw", "XTFN".Copy the code

Example 2:

Input: [" a ", "ab", "ABC", "d", "CD" and "BCD", "abcd"] output: 4: this two word for "ab", the "CD".Copy the code

Example 3:

Input: [" A "," AA "," AAA "," aAAA "] Output: 0 Explanation: There are no such two words.Copy the code

Train of thought

1. Prepare two arrays of N-length masks and lens masks. The masks are used to record the bit mask of a word, and the lens is used to record the length of a word.

Preprocessing, (2) for each character of each string bitMarks | = 1 < < bigNum (chars [I]) operation, get each word a bitmask, and store them in the array masks. Use the array lens to store the length of all words.

3. Compare each word in pairs. If two words do not have a common letter, the maximum word length product Max (taken from lens) is updated. Use an array of masks to determine if two words contain a common letter in constant time :(masks[I] & masks[j]) == 0

class Solution {
	public int maxProduct(String[] words) {
		int max = 0; // The result returned
		int n = words.length;
		int[] masks = new int[n];
		int[] lens = new int[n];
		// 1. Preprocess the bitmask of all words
		int index = 0;
		for (String word : words) {
			char[] chars = word.toCharArray();
			int bitMask = 0;
			for (int i = 0; i < chars.length; i++) {
				bitMask |= 1 << bigNum(chars[i]);
			}
			masks[index] = bitMask;
			lens[index] = word.length();
			index++;
		}
		for (int i = 0; i < n; i++) { // 2. Compare each word in pairs
			for (int j = i + 1; j < n; j++) { // Since j and I have already been compared, we start with I +1
				if ((masks[i] & masks[j]) == 0) { // 3. If the & is 0, the two words do not have the same letter
					max = Math.max(max, lens[i] * lens[j]); // 4. Get the length update Max from lens}}}return max;
	}

	public int bigNum(char c) {
		return (int) c - (int) 'a';
	}


	public static void main(String[] args) {
		String[] words = { "abcw"."baz"."foo"."bar"."xtfn"."abcdef"}; maxProduct1(words); }}Copy the code

Complexity analysis

Time complexity:

Space complexity: