Задача: 1087. Brace Expansion
Сложность: medium

Дан список оценок различных студентов, items, где items[i] = [IDi, scorei] представляет собой одну оценку студента с идентификатором IDi. Вычислите среднее значение пяти лучших оценок каждого студента.

Верните ответ в виде массива пар result, где result[j] = [IDj, topFiveAveragej] представляет студента с идентификатором IDj и его среднее значение пяти лучших оценок. Отсортируйте result по IDj в порядке возрастания.

Среднее значение пяти лучших оценок студента вычисляется путем сложения его пяти лучших оценок и деления на 5 с использованием целочисленного деления.

Пример:

Input: s = "{a,b}c{d,e}f"
Output: ["acdf","acef","bcdf","bcef"]

👨‍💻 Алгоритм:

1⃣Вызовите функцию findAllWords(String, Integer) с данной строкой s и значением startPos равным 0. startPos представляет текущую позицию в строке s. Если строка, которую нужно рассмотреть, пуста (startPos == s.length()), верните список, содержащий пустую строку.

2⃣Вызовите функцию storeFirstOptions с строкой s, целым числом startPos и пустым списком firstOptions. Найдите набор символов, начиная с позиции startPos, и сохраните их в списке firstOptions. Это может быть один символ или все символы между скобками. Отсортируйте список firstOptions. Верните обновленное значение startPos, которое теперь указывает на первый индекс следующей группы символов в строке s, которую мы будем рассматривать. Сохраните это значение в переменной remStringStartPos. Сделайте рекурсивный вызов функции findAllWords(String, Integer) с строкой s и remStringStartPos. Сохраните возвращенный список слов в переменной wordsWithRemString.

3⃣Переберите слова в wordsWithRemString и добавьте вышеуказанный символ в начало каждого слова, сохраняя новую строку в списке expandedWords. Верните список expandedWords.

😎 Решение:

class Solution {
    private int storeFirstOptions(String s, int startPos, List<Character> firstOptions) {
        if (s.charAt(startPos) != '{') {
            firstOptions.add(s.charAt(startPos));
        } else {
            startPos++;
            while (s.charAt(startPos) != '}') {
                if (Character.isLowerCase(s.charAt(startPos))) {
                    firstOptions.add(s.charAt(startPos));
                }
                startPos++;
            }
            Collections.sort(firstOptions);
        }
        return startPos + 1;
    }

    private List<String> findAllWords(String s, int startPos) {
        if (startPos == s.length()) {
            return Arrays.asList("");
        }
        
        List<Character> firstOptions = new ArrayList<>();
        int remStringStartPos = storeFirstOptions(s, startPos, firstOptions);
        List<String> wordsWithRemString = findAllWords(s, remStringStartPos);
        
        List<String> expandedWords = new ArrayList<>();
        for (char c : firstOptions) {
            for (String word : wordsWithRemString) {
                expandedWords.add(c + word);
            }
        }
        return expandedWords;
    }

    public List<String> expand(String s) {
        return findAllWords(s, 0);
    }
}

Ставь 👍 и забирай 📚 Базу знаний