916. Word Subsets

leetcode medium

#array#csharp#hash-table#leetcode#math#medium#string

Task

Вам даны два массива строк words1 и words2. Строка b является подмножеством строки a, если каждая буква в b встречается в ней, включая кратность. Например, "wrr" является подмножеством "warrior", но не является подмножеством "world". Строка a из words1 является универсальной, если для каждой строки b в words2, b является подмножеством a. Верните массив всех универсальных строк в words1. Вы можете вернуть ответ в любом порядке.

Пример:

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

Output: ["facebook","google","leetcode"]

C# solution

matched/original

using System;
using System.Collections.Generic;
using System.Linq;
public class Solution {
    public IList<string> WordSubsets(string[] words1, string[] words2) {
        int[] maxCount = new int[26];
        foreach (string word in words2) {
            int[] count = GetCount(word);
            for (int i = 0; i < 26; i++) {
                maxCount[i] = Math.Max(maxCount[i], count[i]);
            }
        }
        List<string> result = new List<string>();
        foreach (string word in words1) {
            int[] count = GetCount(word);
            if (IsUniversal(count, maxCount)) {
                result.Add(word);
            }
        }
        return result;
    }
    private int[] GetCount(string word) {
        int[] count = new int[26];
        foreach (char c in word) {
            count[c - 'a']++;
        }
        return count;
    }
    private bool IsUniversal(int[] count, int[] maxCount) {
        for (int i = 0; i < 26; i++) {
            if (count[i] < maxCount[i]) {
                return false;
            }
        }
        return true;
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<string> WordSubsets(vector<string> words1, vector<string> words2) {
        vector<int>& maxCount = new int[26];
        foreach (string word in words2) {
            vector<int>& count = GetCount(word);
            for (int i = 0; i < 26; i++) {
                maxCount[i] = max(maxCount[i], count[i]);
            }
        }
        List<string> result = new List<string>();
        foreach (string word in words1) {
            vector<int>& count = GetCount(word);
            if (IsUniversal(count, maxCount)) {
                result.push_back(word);
            }
        }
        return result;
    }
    private vector<int>& GetCount(string word) {
        vector<int>& count = new int[26];
        foreach (char c in word) {
            count[c - 'a']++;
        }
        return count;
    }
    private bool IsUniversal(vector<int>& count, vector<int>& maxCount) {
        for (int i = 0; i < 26; i++) {
            if (count[i] < maxCount[i]) {
                return false;
            }
        }
        return true;
    }
}

Java solution

matched/original

import java.util.*;

class Solution {
    public List<String> wordSubsets(String[] words1, String[] words2) {
        int[] maxCount = new int[26];
        for (String word : words2) {
            int[] count = getCount(word);
            for (int i = 0; i < 26; i++) {
                maxCount[i] = Math.max(maxCount[i], count[i]);
            }
        }

        List<String> result = new ArrayList<>();
        for (String word : words1) {
            int[] count = getCount(word);
            if (isUniversal(count, maxCount)) {
                result.add(word);
            }
        }
        
        return result;
    }

    private int[] getCount(String word) {
        int[] count = new int[26];
        for (char c : word.toCharArray()) {
            count[c - 'a']++;
        }
        return count;
    }

    private boolean isUniversal(int[] count, int[] maxCount) {
        for (int i = 0; i < 26; i++) {
            if (count[i] < maxCount[i]) {
                return false;
            }
        }
        return true;
    }
}

JavaScript solution

matched/original

var wordSubsets = function(words1, words2) {
    const getCount = (word) => {
        const count = {};
        for (const char of word) {
            count[char] = (count[char] || 0) + 1;
        }
        return count;
    };
    
    const maxCount = {};
    for (const word of words2) {
        const count = getCount(word);
        for (const char in count) {
            maxCount[char] = Math.max(maxCount[char] || 0, count[char]);
        }
    }

    return words1.filter(word => {
        const count = getCount(word);
        return Object.keys(maxCount).every(char => count[char] >= maxCount[char]);
    });
};

Python solution

matched/original

from collections import Counter

def wordSubsets(words1, words2):
    def count(word):
        return Counter(word)

    max_count = Counter()
    for word in words2:
        for char, cnt in count(word).items():
            max_count[char] = max(max_count[char], cnt)

    result = []
    for word in words1:
        word_count = count(word)
        if all(word_count[char] >= max_count[char] for char in max_count):
            result.append(word)

    return result

Go solution

matched/original

package main

func wordSubsets(words1 []string, words2 []string) []string {
    maxCount := make([]int, 26)
    for _, word := range words2 {
        count := getCount(word)
        for i := 0; i < 26; i++ {
            if count[i] > maxCount[i] {
                maxCount[i] = count[i]
            }
        }
    }

    result := []string{}
    for _, word := range words1 {
        count := getCount(word)
        if isUniversal(count, maxCount) {
            result = append(result, word)
        }
    }

    return result
}

func getCount(word string) []int {
    count := make([]int, 26)
    for _, char := range word {
        count[char-'a']++
    }
    return count
}

func isUniversal(count []int, maxCount []int) bool {
    for i := 0; i < 26; i++ {
        if count[i] < maxCount[i] {
            return false
        }
    }
    return true
}

Explanation

Algorithm

1⃣Подсчитать максимальное количество каждой буквы в каждом слове из words2.

2⃣Проверить каждое слово из words1, если оно содержит не менее максимального количества каждой буквы, которая встречается в словах из words2.

3⃣Вернуть массив слов из words1, которые удовлетворяют этому условию.

😎