This is the 17th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

The title

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.

The sample

Input: [abcw ", "" baz", "foo", "bar", "XTFN", "abcdef"] output: 16 explanation: the two words "abcw", "XTFN".Copy the code
Input: [" a ", "ab", "ABC", "d", "CD" and "BCD", "abcd"] output: 4: this two word for "ab", the "CD".Copy the code
Input: [" A "," AA "," AAA "," aAAA "] Output: 0 Explanation: There are no such two words.Copy the code

prompt

  • 2 <= words.length <= 1000
  • 1 <= words[i].length <= 1000
  • words[i]Contains only lowercase letters

Their thinking

An operation

The violent solution is to iterate through two layers, and then determine separately whether each string has a common letter with other strings. This time complexity is too high, resulting in a timeout.

In the brute force method, we need to calculate each element in the string each time, so we can find a variable, save the result of the calculation, and use it directly when we need to use it later, so that we do not have to repeat the calculation operation.

At the same time, since the words array only contains lower-case letters with only 26 bits, we can make use of binary features to quickly figure out whether two strings have common letters through and operation.

class Solution {
    public int maxProduct(String[] words) {
        int n = words.length;
        // Define an array that holds the letters of each string
        int[] arr = new int[n];
        for(int i = 0; i < n; ++i){
            int tmp = 0;
            // Iterate over the string
            for(char w : words[i].toCharArray()){
                // Mark the corresponding element as 1
                tmp |= (1 << (w - 'a'));
            }
            / / assignment
            arr[i] = tmp;
        }

        / / Max
        int max = 0;
        
        // Compare the string to other strings in the array
        for(int i = 0; i < n; ++i){
            for(int j = 0; j < n; ++j){
                // If there are no public letters, the maximum value is updated
                if((arr[i] & arr[j]) == 0){ max = Math.max(max, words[i].length() * words[j].length()); }}}// Return the result
        returnmax; }}Copy the code

Complexity analysis

  • O(N2)O(N^2)O(N2)
  • Space complexity: O(N)O(N)O(N)

The last

The article has written the bad place, asks the big guys to be generous to give advice, the mistake is the most can let the person grow up, wishes me and the big guy the distance to shorten gradually!

If you feel the article is helpful to you, please click like, favorites, follow, comment four consecutive support, your support is the biggest power of my creation!!

Title source: leetcode-cn.com/problems/ma…