916.word-subsets.md

916. Word Subsets

Hash Table

We add word1[i] if every word in word2 exists in it. But we don't need to check every character in word2 for every word in word1.

word1 = ["aaaaaaaa", ...]
word2 = ["aaa", "aaaa", "a"]

We don't check "aaa", "aaaa", "a" for every word in word1. We just merge them into a single word and check if every character in this merged word exists in word1. We can only check the maximum frequency of each character in word2 and then check if it exists in word1.

For example, for ["aaa", "aaaa", "a"], we only need to check if word1 contains max(3, 4, 1) = 4 a's.

fun wordSubsets(words1: Array<String>, words2: Array<String>): List<String> {
    val n = words2.size
    val count2 = IntArray(26)
    for (i in words2.indices) {
        val word = words2[i]
        val currentCount = IntArray(26)
        for (c in word) {
            currentCount[c - 'a']++
        }
        for (i in 0 until 26) {
            count2[i] = maxOf(count2[i], currentCount[i])
        }
    }
    val universal = mutableListOf<String>()
    for (word in words1) {
        val count1 = IntArray(26)
        for (c in word) {
            count1[c - 'a']++
        }

        if (isSubset(count1, count2)) {
            universal.add(word)
        }
    }
    return universal
}

private fun isSubset(a: IntArray, b: IntArray): Boolean {
    for (i in 0 until 26) {
        if (a[i] < b[i]) return false
    }
    return true
}

• Time Complexity: O(N + M), where N is the total number of characters in words2 and M is the total number of characters in words1.
• Space Complexity: O(1). We use a constant space for the two arrays of size 26.