Nano Hash - криптовалюты, майнинг, программирование

Оптимальное решение для разбиения строки на три палиндрома с самыми ранними разрезами

Мне задали этот вопрос в интервью:

Имея строку (1‹=|s|‹=10^5), проверьте, можно ли разбить ее на три палиндрома. Если возможных ответов несколько, выведите тот, в котором разрезы сделаны раньше. Если ответ невозможен, выведите «Impossible».

**Input:**

radarnoonlevel

aabab

abcdefg

**Output:**

radar noon level

a a bab   (Notice how a, aba, b is also an answer, but we will output the one with the earliest cuts)

Impossible

Я смог дать решение грубой силы, запустив два цикла и проверив свойство палиндрома для каждых 3 подстрок (0-i, i-j, j-end). Это было явно не оптимально, но с тех пор я не смог найти лучшего решения.

Мне нужен способ проверки того, что если я знаю свойство палиндрома строки, то как удаление символа в начале или добавление символа в конце может дать мне свойство новой строки без необходимости выполнять проверку для всей строки опять таки. Я думаю об использовании трех карт, где каждая клавиша символа сопоставляется с количеством вхождений, но это тоже меня ни к чему не приводит.

string palindrome
01.06.2020

Ответы:


1

Все еще решение O (n ^ 2), но вы можете сохранить результат подстрок палиндрома в таблице и использовать его для получения ответа.

vector<string> threePalindromicSubstrings(string word) {
    int n = word.size();
    vector<vector<bool>> dp (n,vector<bool>(n,false));
    for(int i = 0 ; i < n ; ++i)
        dp[i][i] = 1;
    
    for(int l = 2 ; l <= n ; ++l){
        for(int i = 0 ; i < n - l +1 ; ++i){
            int j = i + l - 1;
            if(l == 2)
                dp[i][j] = (word[i] == word[j]);
            else
                dp[i][j] = (word[i] == word[j]) && (dp[i+1][j-1]);
        }
    }

    vector<string> ans;
    for(int i = 0 ; i < n - 2 ; ++i){
        if(dp[0][i]) {
            for(int j = i+1 ; j < n - 1 ; ++j){
                if(dp[i+1][j] && dp[j+1][n-1]){
                    ans.push_back(word.substr(0,i + 1));
                    ans.push_back(word.substr(i+1,j-i));
                    ans.push_back(word.substr(j+1,n-j));
                    return ans;
                }
            }
        }
    }
    if(ans.empty())
        ans.push_back("Impossible");
    return ans;
}
09.08.2020
Новые материалы
Кластеризация: более глубокий взгляд
Кластеризация — это метод обучения без учителя, в котором мы пытаемся найти группы в наборе данных на основе некоторых известных или неизвестных свойств, которые могут существовать. Независимо от..
Как написать эффективное резюме
Предложения по дизайну и макету, чтобы представить себя профессионально Вам не позвонили на собеседование после того, как вы несколько раз подали заявку на работу своей мечты? У вас может..
Частный метод Python: улучшение инкапсуляции и безопасности
Введение Python — универсальный и мощный язык программирования, известный своей простотой и удобством использования. Одной из ключевых особенностей, отличающих Python от других языков, является..
Как я автоматизирую тестирование с помощью Jest
Шутка для победы, когда дело касается автоматизации тестирования Одной очень важной частью разработки программного обеспечения является автоматизация тестирования, поскольку она создает..
Работа с векторными символическими архитектурами, часть 4 (искусственный интеллект)
Hyperseed: неконтролируемое обучение с векторными символическими архитектурами (arXiv) Автор: Евгений Осипов , Сачин Кахавала , Диланта Хапутантри , Тимал Кемпития , Дасвин Де Сильва ,..
Понимание расстояния Вассерштейна: мощная метрика в машинном обучении
В обширной области машинного обучения часто возникает необходимость сравнивать и измерять различия между распределениями вероятностей. Традиционные метрики расстояния, такие как евклидово..
Обеспечение масштабируемости LLM: облачный анализ с помощью AWS Fargate и Copilot
В динамичной области искусственного интеллекта все большее распространение получают модели больших языков (LLM). Они жизненно важны для различных приложений, таких как интеллектуальные..