Запишите функцию, которая возвращает самый длинный палиндром в данной строке

например, "ccddcc" в строке "abaccddccefe"

Я думал о решении, но оно выполняет в O (n^2) время

Алгоритм 1:

Шаги: это - метод грубой силы

  1. Имейте 2 для циклов
    поскольку я = 1 мне меньше, чем array.length-1
    для j=i+1 к j меньше, чем array.length
  2. Таким образом, можно получить подстроку каждой возможной комбинации от массива
  3. Имейте функцию палиндрома, которая проверяет, является ли строка палиндромом
  4. таким образом для каждой подстроки (я, j) вызывают эту функцию, если это - палиндром, хранят его в строковой переменной
  5. При нахождении следующей подстроки палиндрома и если это больше, чем текущее, замените его текущим.
  6. Наконец Ваша строковая переменная будет иметь ответ

Проблемы: 1. Этот алгоритм выполняет в O (n^2) время.

Алгоритм 2:

  1. Инвертируйте строку и сохраните ее в другом массиве
  2. Теперь найдите самую большую подстроку соответствия между обоими массивом
  3. Но это также выполняет в O (n^2) время

Можете Вы парни думать об алгоритме, который работает в лучшее время. Если возможно O (n) время

101
задан casperOne 29 June 2012 в 11:54
поделиться

1 ответ

Недавно мне задали этот вопрос. Вот решение, которое я [в конце концов] придумал. Я сделал это на JavaScript, потому что это довольно просто на этом языке.

Основная концепция заключается в том, что вы просматриваете строку в поисках наименьшего возможного многосимвольного палиндрома (двух- или трехсимвольного). Получив его, расширяйте границы с обеих сторон до тех пор, пока он не перестанет быть палиндромом. Если эта длина больше, чем текущая самая длинная, сохраните ее и двигайтесь дальше.

// This does the expanding bit.
function getsize(s, start, end) {
    var count = 0, i, j;
    for (i = start, j = end; i >= 0 && j < s.length; i--, j++) {
        if (s[i] !== s[j]) {
            return count;
        }
        count = j - i + 1; // keeps track of how big the palindrome is
    }
    return count;
}

function getBiggestPalindrome(s) {
    // test for simple cases
    if (s === null || s === '') { return 0; }
    if (s.length === 1) { return 1; }
    var longest = 1;
    for (var i = 0; i < s.length - 1; i++) {
        var c = s[i]; // the current letter
        var l; // length of the palindrome
        if (s[i] === s[i+1]) { // this is a 2 letter palindrome
            l = getsize(s, i, i+1);
        }
        if (i+2 < s.length && s[i] === s[i+2]) { // 3 letter palindrome
            l = getsize(s, i+1, i+1);
        }
        if (l > longest) { longest = l; }
    }
    return longest;
}

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

1
ответ дан 24 November 2019 в 04:45
поделиться
Другие вопросы по тегам:

Похожие вопросы: