“This is the 17th day of my participation in the Gwen Challenge in November. See details of the event: The Last Gwen Challenge in 2021”.

Topic describes

This is 318 on LeetCode. Maximum word length product with medium difficulty.

Tag: “simulation”, “bit operation”, “hash table”

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 000.

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

Tip:

  • 2 <= words.length <= 1000
  • 1 <= words[i].length <= 1000
  • Words [I] contains only lowercase letters

simulation

Words [I] Words [I]words[I] only have lowercase letters, and only need to distinguish between two characters whether there is letter duplication.

We can use an int to refer to a word[I]word[I]word[I] : low 262626 to refer to whether the letters A-z have been present.

Then the & operation is performed on the two int values corresponding to each “character pair” (the result is 000 if there are no duplicate characters) and the final answer is obtained.

Code:

class Solution {
    public int maxProduct(String[] words) {
        int n = words.length, idx = 0;
        int[] masks = new int[n];
        for (String w : words) {
            int t = 0;
            for (int i = 0; i < w.length(); i++) {
                int u = w.charAt(i) - 'a';
                t |= (1 << u);
            }
            masks[idx++] = t;
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if ((masks[i] & masks[j]) == 0) ans = Math.max(ans, words[i].length() * words[j].length()); }}returnans; }}Copy the code
  • Time complexity: Let NNN be the length of the WordsWordsWords array, The complexity of maskSMAskSMasks is O(∑ I =0i=n−1words[I].length)O(\sum_{I =0}^{I =n – 1} words [I]. Length) O (∑ I = 0 I = n – 1 words [I] length); The answer is O(n2)O(n^2)O(n2). The overall complexity of O (Max ⁡ (∑ I = 0 I = n – 1 words [I] length, n2)) O (\ Max (\ sum_ {I = 0} ^} {I = n – 1 words [I] length, N ^ 2) O (Max (∑ I = 0 I = n – 1 words [I] length, n2))
  • Space complexity: O(n)O(n)O(n)

To optimize the

It is not difficult to find that for the two characters with the same word frequency (maskMaskMask value is the same), only the characters with large length need to be reserved. Therefore, we can use “hash table” to replace maskSMAskSMasks array.

Code:

class Solution {
    public int maxProduct(String[] words) {
        Map<Integer, Integer> map = new HashMap<>();
        for (String w : words) {
            int t = 0, m = w.length();
            for (int i = 0; i < m; i++) {
                int u = w.charAt(i) - 'a';
                t |= (1 << u);
            }
            if(! map.containsKey(t) || map.get(t) < m) map.put(t, m); }int ans = 0;
        for (int a : map.keySet()) {
            for (int b : map.keySet()) {
                if ((a & b) == 0) ans = Math.max(ans, map.get(a) * map.get(b)); }}returnans; }}Copy the code
  • Time complexity: Let NNN be the length of the WordsWordsWords array, The complexity of mapMapMap is O(∑ I =0i=n−1words[I].length)O(\sum_{I =0}^{I = n-1}words[I].length)O(∑ I =0i=n−1words[I].length); The answer is O(n2)O(n^2)O(n2). The overall complexity of O (Max ⁡ (∑ I = 0 I = n – 1 words [I] length, n2)) O (\ Max (\ sum_ {I = 0} ^} {I = n – 1 words [I] length, N ^ 2) O (Max (∑ I = 0 I = n – 1 words [I] length, n2))
  • Space complexity: O(n)O(n)O(n)

The last

This is the no.318 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 questions on LeetCode as of the start date, some of which have lock questions. We will finish all the questions without lock first.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour…

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.