PattySung

You are given two string arrays words1 and words2.

A string b is a subset of string a if every letter in b occurs in a including multiplicity.

For example, “wrr” is a subset of “warrior” but is not a subset of “world”. A string a from words1 is universal if for every string b in words2, b is a subset of a.

Return an array of all the universal strings in words1. You may return the answer in any order.

Example 1:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["e","o"]
Output: ["facebook","google","leetcode"]

Example 2:

Input: words1 = ["amazon","apple","facebook","google","leetcode"], words2 = ["l","e"]
Output: ["apple","google","leetcode"]

<解題>優化後的解法

用get_char_frequency方法，去計算words各字母出現的頻率。
用char的方式去計算words2各字母出現的最大頻率，同時遍歷words1的頻率去比對，沒有不符合的，就加入result這個arraylist裏面

class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        //計算words2各字母的頻率
        int[] max_b_frequencies = new int[26];
        
        for (String word : words2) {
            int[] char_frequency = get_char_frequency(word);
            for (int j = 0; j < 26; j++) {
                max_b_frequencies[j] = Math.max(max_b_frequencies[j], char_frequency[j]);
            }
        }

        //遍歷words1的頻率去比對
        List<String> result = new ArrayList<>();
        for (String word : words1) {
            int[] char_count = get_char_frequency(word);
            
            boolean valid = true;
            for (int j = 0; j < 26; j++) {
                if (char_count[j] < max_b_frequencies[j]) {
                    valid = false;
                    break;
                }
            }
            if (valid) {
                result.add(word);
            }
        }
        
        return result;
    }

    public int[] get_char_frequency(String s) {
        int[] result = new int[26];
        for (char c : s.toCharArray()) {
            result[c - 'a']++;
        }
        return result;
    }
}


class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        List<String> result = new ArrayList();
        
        int[] max_b_frequencies = new int[26];

        //計算words2部分
        for(int i =0 ;i<words2.length;i++){
            String current_word = words2[i];
            int[] char_frequency = get_char_frequency(current_word); //words2中每個String的字母頻率
            for(int j = 0 ; j<26; j++){ //每次更新每個字母最多的最高頻率
                max_b_frequencies[j] = Math.max(max_b_frequencies[j], char_frequency[j]);
            }
        }
        //計算words1部分
        for(int i =0; i<words1.length; i++){
            String current_word = words1[i];
            int[] char_count = get_char_frequency(current_word);//words1中每個String的字母頻率

            boolean valid= true;
            for(int j = 0 ; j<26; j++){
                if(max_b_frequencies[j] > char_count[j]){
                    valid = false;
                    break;
                }
            }
            if(valid) {
                result.add(current_word);
            }
        }
        return result;
    }

    public int[] get_char_frequency(String s){
        int[] result = new int[26];
        for(char c : s.toCharArray()){
            result[c-'a']++;
        }
        return result;
    }
}

Time: O((M+N)*K) Space: O(N)

Leetcode-916. Word Subsets

<解題>優化後的解法