916. Word Subsets

 一刷 07/2022

Version #1 Array as HashMap

Time O(M + N)

Space O(1)

Runtime: 26 ms, faster than 86.18% of Java online submissions for Word Subsets.

Memory Usage: 89.1 MB, less than 52.85% of Java online submissions for Word Subsets.

class Solution {

    public List<String> wordSubsets(String[] words1, String[] words2) {

        // calculate the maximum counter of each character in words2

        // the counter of characters in words1 need to be at least larger than or equals to the maximum counter of words2

        int[] maxCount = new int[26];

        for (String word : words2) {

            int[] count = new int[26];

            for (int i = 0; i < word.length(); i++) {

                int index = word.charAt(i) - 'a';

                count[index]++;

                maxCount[index] = Math.max(maxCount[index], count[index]);

            }

        }

        List<String> result = new ArrayList<>();

        for (String word : words1) {

            int[] count = new int[26];

            for (int i = 0; i < word.length(); i++) {

                count[word.charAt(i) - 'a']++;

            }

            int i = 0;

            for (i = 0; i < 26; i++) {

                if (count[i] < maxCount[i]) {

                    break;

                }

            }

            if (i == 26) {

                result.add(word);

            }

        }

        return result;

    }

}