Возврат набора всех слов в списке слов, которые могут быть сделаны с подмножеством входных символов

Question

Я работаю над приведенной ниже проблемой, но не могу понять, как решить эту проблему в Java?

Учитывая массив символов, возвращает набор всех слов в списке словэто может быть сделано с любым подмножеством этих символов.Дубликаты могут присутствовать в массиве, но каждый индекс массива может использоваться только один раз для каждого слова.Таким образом, при наличии {'o', 'r', 's', 'd', 'o', 'w', 'e'} вы можете вернуть (среди прочих) слова "word", "words" и "wood"", но не" заказ ".

class Finder {

  public void init(Set<String> words) {

  }

  public Set<String> find(List<Character> chars) {

  }
}

Какая должна быть идея для решения такого рода проблем?

Answer 1

Вот один из возможных подходов:

1. создайте массив count / map / hashtable, чтобы подсчитать, сколько у вас каждого символа, так в примере вы дали это будет cnt['o']=2, cnt['r']=1, cnt['s']=1 и так далее

2. Переберите все слова и для каждого слова создайте другую структуру массива счетчиков, назовите ее cnt2

3. Слово можно составить, только если cnt[x] >= cnt2[x] для всех отдельных букв слова

4. Соберите все слова, удовлетворяющие этому свойству, и поместите их в набор

Answer 2

Вот еще один подход, использующий Collection.remove(Object o), который возвращает логическое значение:

private static boolean canBeDoneWith(String word, List<Character> chars) {
    List<Character> temp = new ArrayList<>(chars);
    for (char c: word.toCharArray()) {
        if (!temp.remove(Character.valueOf(c))) {
            return false;
        }
    }
    return true;
}

Метод find становится:

public Set<String> find(List<Character> chars) {
    Set<String> result = new HashSet<>();
    for (String word: words) {
        if (canBeDoneWith(word, chars)) {
            result.add(word);
        }
    }
    return result;
}