Задача: 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 function storeFirstOptions($s, $startPos, &$firstOptions) {
        if ($s[$startPos] != '{') {
            $firstOptions[] = $s[$startPos];
        } else {
            $startPos++;
            while ($s[$startPos] != '}') {
                if ($s[$startPos] >= 'a' && $s[$startPos] <= 'z') {
                    $firstOptions[] = $s[$startPos];
                }
                $startPos++;
            }
            sort($firstOptions);
        }
        return $startPos + 1;
    }

    private function findAllWords($s, $startPos) {
        if ($startPos == strlen($s)) {
            return [""];
        }

        $firstOptions = [];
        $remStringStartPos = $this->storeFirstOptions($s, $startPos, $firstOptions);
        $wordsWithRemString = $this->findAllWords($s, $remStringStartPos);

        $expandedWords = [];
        foreach ($firstOptions as $c) {
            foreach ($wordsWithRemString as $word) {
                $expandedWords[] = $c . $word;
            }
        }
        return $expandedWords;
    }

    public function expand($s) {
        return $this->findAllWords($s, 0);
    }
}

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