솔루션: 단어 길이의 최대 곱

이것은 일련의 Leetcode 솔루션 설명( )의 일부입니다. 이 솔루션이 마음에 드셨거나 유용하셨다면 이 게시물에 좋아요를 누르거나 추천my solution post on Leetcode's forums 해주세요.

Leetcode 문제 #318(중간): 단어 길이의 최대 곱

설명:

(이동: Solution Idea || 코드: JavaScript | Python | Java | C++ )

Given a string array words, return the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. If no such two words exist, return 0.

예:

Example 1:
Input:	words = ["abcw","baz","foo","bar","xtfn","abcdef"]
Output:	16
Explanation:	The two words can be "abcw", "xtfn".

Example 2:
Input:	words = ["a","ab","abc","d","cd","bcd","abcd"]
Output:	4
Explanation:	The two words can be "ab", "cd".

Example 3:
Input:	words = ["a","aa","aaa","aaaa"]
Output:	0
Explanation:	No such pair of words.

제약 조건:

• 2 <= words.length <= 1000
• 1 <= words[i].length <= 1000
• words[i] consists only of lowercase English letters.

아이디어:

(이동: Problem Description || 코드: JavaScript | Python | Java | C++ )

이 문제의 명백한 첫 번째 관심사는 두 단어에 동일한 문자가 포함되어 있는지 평가하는 것입니다. 이것은 자연스럽게 각 단어의 문자 집합을 만들어야 하지만 이러한 집합을 비교하는 것은 여전히 ​​쉽지 않습니다.

그러나 비트 조작을 사용하여 문자 비트 집합을 만드는 경우 비트 AND(&)를 사용하여 0이 아닌 결과가 겹치는 문자를 의미하는 두 비트 집합 정수를 비교하는 것이 충분히 쉬워야 합니다.

이 솔루션은 단어의 각 조합을 함께 비교해야 하기 때문에 여전히 최소한 O(N^2)의 시간 복잡도를 요구합니다. 먼저 길이를 기준으로 단어를 정렬하여 이를 조금 더 최적화할 수 있습니다. 그러면 더 큰 제품을 더 빨리 찾을 수 있습니다. 사실, 정렬된 단어를 반복하면서 단어가 더 이상 최상의 결과를 생성할 수 없을 때를 분리할 수 있으며, 그 시점에서 즉시 최상의 결과를 반환할 수 있습니다.

또한 비교를 시작하기 전에 각 단어를 비트 집합으로 변환할 필요가 없습니다. 각 단어를 bitset으로 변환하는 작업을 마치면 bitset에 저장된 이전에 완료된 모든 결과와 비교할 수 있습니다.

현재 bitset 비교를 마친 후에는 이후 결과와 비교하기 위해 bitset 배열에 추가할 수 있습니다.

시간 복잡도: O(N^2 + N*M) 여기서 N은 단어의 길이이고 M은 단어의 평균 길이입니다.

공간 복잡도: 비트 집합의 경우 O(N)

구현:

비트 집합과 단어 길이가 비교 전에 사전에 키 값 쌍으로 함께 저장되면 Python이 이상하게 빠릅니다.

Java 및 C++ 정렬은 적어도 주어진 테스트 스위트에서는 효과적인 최적화가 되지 않을 만큼 충분히 느립니다.

자바스크립트 코드:

(이동: Problem Description || Solution Idea )

var maxProduct = function(words) {
    words.sort((a,b) => b.length - a.length)
    let best = 0, bitsets = new Uint32Array(words.length)
    for (let i = 0; i < words.length; i++) {
        let word = words[i], wlen = word.length, bitset = 0
        if (wlen * words[0].length < best)
            return best
        for (let j = 0; j < wlen; j++)
            bitset |= 1 << (word.charCodeAt(j) - 97)
        for (let j = 0; j < i; j++)
            if ((bitsets[j] & bitset) === 0)
                best = Math.max(best, wlen * words[j].length)
        bitsets[i] = bitset
    }
    return best
};

파이썬 코드:

(이동: Problem Description || Solution Idea )

class Solution:
    def maxProduct(self, words: List[str]) -> int:
        words.sort(key=len, reverse=True)
        best, bitsets = 0, {}
        for i in range(len(words)):
            wlen, bitset = len(words[i]), 0
            if wlen * len(words[0]) < best:
                return best
            for c in words[i]:
                bitset |= 1 << ord(c) - 97
            if bitset not in bitsets:
                for k,v in bitsets.items():
                    if not bitset & k:
                        best = max(best, wlen * v)
                bitsets[bitset] = wlen
        return best

자바 코드:

(이동: Problem Description || Solution Idea )

class Solution {
    public int maxProduct(String[] words) {
        int best = 0;
        int[] bitsets = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            int wlen = words[i].length(), bitset = 0;
            for (int j = 0; j < wlen; j++)
                bitset |= 1 << (words[i].charAt(j) - 'a');
            for (int j = 0; j < i; j++)
                if ((bitsets[j] & bitset) == 0)
                    best = Math.max(best, wlen * words[j].length());
            bitsets[i] = bitset;
        }
        return best;
    }
}

C++ 코드:

(이동: Problem Description || Solution Idea )

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