Construct the optimal solution using the optimal substructure matrix Your task is to implement the following function for constructing the optimal solution to the LCS problem with the optimal substructure matrix: def get_optimal_solution(string_a: str, optimal_substructure_matrix: List[List[int]]) -> str: “””Given an optimal substructure matrix, the first string returns the optimal solution to the LCS problem. NOTE: if there are multiple optimal solutions, feel free to return any of them.

Даны две строки string_a и string_b. Необходимо построить оптимальное решение для задачи наибольшей общей подпоследовательности (LCS) с использованием матрицы оптимальной подструктуры optimal_substructure_matrix.

LCS – это наибольшая общая подпоследовательность двух строк, то есть наибольшая последовательность символов, которая присутствует в обеих строках в том же порядке.

Функция get_optimal_solution должна вернуть оптимальное решение для данной задачи.

Шаги решения:
1. Инициализируем пустую строку result.
2. Находим размеры матрицы optimal_substructure_matrix, представляющей результаты промежуточных подзадач.
3. Используем два указателя i и j, начиная с конца строк string_a и string_b.
4. Пока i и j больше нуля:
– Если string_a[i-1] равно string_b[j-1], то добавляем символ string_a[i-1] в начало строки result и уменьшаем i и j на единицу.
– Иначе, если значение optimal_substructure_matrix[i][j] равно optimal_substructure_matrix[i-1][j], то уменьшаем i на единицу.
– Иначе, если значение optimal_substructure_matrix[i][j] равно optimal_substructure_matrix[i][j-1], то уменьшаем j на единицу.
5. Возвращаем полученную строку result.
Поскольку LCS может иметь несколько оптимальных решений, результат может быть любым из них.