Сложность: hard
Вам дан список эквивалентных пар строк synonyms, где synonyms[i] = [si, ti] означает, что si и ti являются эквивалентными строками. Вам также дан текст предложения. Верните все возможные синонимичные предложения, отсортированные лексикографически.
Пример:
Input: numPeople = 4
Output: 2
👨💻 Алгоритм:
1⃣Определим массив для хранения каталановых чисел.
2⃣Заполним массив каталановых чисел с помощью рекуррентной формулы.
3⃣Вернем 𝐶𝑛𝑢𝑚𝑃𝑒𝑜𝑝𝑙𝑒/2C.
😎 Решение:
def numHandshakes(numPeople):
n = numPeople // 2
catalan = [0] * (n + 1)
catalan[0] = 1
for i in range(1, n + 1):
for j in range(i):
catalan[i] += catalan[j] * catalan[i - 1 - j]
return catalan[n]
Ставь 👍 и забирай 📚 Базу знаний