JAVA----------Easy Version To Understand!!!!!!!!!!!!!!!!!


  • 212
    H
    	public static int maxProduct(String[] words) {
    	if (words == null || words.length == 0)
    		return 0;
    	int len = words.length;
    	int[] value = new int[len];
    	for (int i = 0; i < len; i++) {
    		String tmp = words[i];
    		value[i] = 0;
    		for (int j = 0; j < tmp.length(); j++) {
    			value[i] |= 1 << (tmp.charAt(j) - 'a');
    		}
    	}
    	int maxProduct = 0;
    	for (int i = 0; i < len; i++)
    		for (int j = i + 1; j < len; j++) {
    			if ((value[i] & value[j]) == 0 && (words[i].length() * words[j].length() > maxProduct))
    				maxProduct = words[i].length() * words[j].length();
    		}
    	return maxProduct;
    }

  • 23
    P

    Hi, could you explain a little bit on how this part works?

    value[i] |= 1 << (tmp.charAt(j) - 'a');

  • 42
    H

    ok,int has 32bits,but lower case letters only has 26 .we can use the lowest 26 bit of int indicates that the word has how many kinds of lower case letters .If the lowest bit of int is 1,it indicates the word has lower case letter 'a'.......the order of lower case letter is from right to left,like zyx.....cba.so value[i] indicates the condition of the word i having how many kinds of lower case letters .please vote me for this problem! If you have any question ,please follow up!


  • 0
    W

    The reason use 1<< is that let the value of 'a' to be 1?
    And is that possible that different characters and different length might create the same value? I am still confused. Thank you in advance.

    Oh I figured out by myself. Thank you anyway.


  • 23
    X

    Answer user wwtwxlwjh question.

    The reason use 1<< is that let the value of 'a' to be 1?
    Yes, otherwise, 'a' will be missed since 'a' - 'a' = 0.

    And is that possible that different characters and different length might create the same value?

    Short Answer is Yes if I understand your problem correctly.

    Example, "abcd" and "aabbccdd" will both return 0000 ***0 1111

    you should know, we don't care how many times of a character occurs in one word, we just want to record what letters occurs in one word, so that we can use AND operation to compare if two words has the same letter afterwards.

    for prior case, 0000 ***0 1111 & 0000 ***0 1111 equals to **** 1111 which means has same letter.

    another case would be "abcd" and "efgh",

    0000 **** 0000 1111 & 0000 **** 1111 0000 equals to 0000 **** 0000, which means these two words don't have same letters.


  • 0
    Y

    Thank you, it helps me a lot!


  • 0
    G

    Thanks for providing this easy-to-understand solution. I have a question about the 1st line: what is the difference between words.length == 0 and words == null? I thought they were the same... Can you help me to tell the difference?


  • 3
    S

    "words == null" means you haven't allocate any memory to it. (i.e. "words" is a null pointer)..."words.length == 0" means "words" points to a memory block but there is nothing in it. If you only write "words.length == 0" in the if statement and "words" turns out to be a null pointer, the program will throw NullPointerException.


  • 0
    G

    OK, I got it. Thanks : )


  • 0
    L

    @HelloWorld123456 Amazingly good. Loved the concept of using 32 bits instead of Map/Set.


  • 2
    J

    @HelloWorld123456 Great solution! Using the value vector to indicate the containing characters. upvoted

    Here is the c++ version

    class Solution {
    public:
        int maxProduct(vector<string>& words) {
            vector<int> value(words.size(), 0);
            for(int i = 0; i < words.size(); ++i)
                for(auto c: words[i])
                    value[i] |= 1 << (c - 'a');
    
            int ret = 0;
            for(int i = 1; i < words.size(); ++i)
                for(int j = 0; j < i; ++j)
                    if((value[i] & value[j]) == 0 && words[i].length() * words[j].length() > ret)
                        ret = words[i].length() * words[j].length();
            return ret;
        }
    };
    
    

  • 4
    J

    @pei-heng Each integer in an array is of size 32 bits long(which is >26). So in short we are just setting every bit of an integer. So for example "abcw": set 0,1,2,23 bit. (1<<('a'-'a')) = 1<<0 which is 1, (1<<('w'-'a'))==2^23 and so on


  • 0
    X

    @HelloWorld123456 Your solution and explanation are awwwwwwwwwesome!!!!!! Thanks!!!!! I always thought of using HashMap at first. This is using one integer to instead Redundant HashMap.


  • 0
    T

    hi, i'm pretty new to this but i perfectly understand the concept. just don't know what "|=" is. Does it store the value as binary ?


  • 0
    X

    @tomle125 Same as +=, -=, *=,
    a|=b means a = a|b


  • 0
    T

    @xiaoyaoworm ohhhh thanks. it makes sense.


  • 1
    S

    What if the words is not just consist of letters but possible char between 0-255


  • 0
    C

    whats the time complexity of this solution??
    is it O(max(n^2, l^2)) where n is words size and l is max word size


  • 1
    S

    @code4life I think it shoud be O(max(n^2, n*L)) where L is the max word length.


  • 0
    H

    I am not clear about why we need to check "words[i].length() * words[j].length() > maxProduct"? we can get max just by using the following,
    if ((value[i] & value[j]) == 0 ) maxProduct = words[i].length() * words[j].length();
    Thanks~


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.