Вопрос:
Вопрос:
Для любой строки добавьте наименьшее количество символов, чтобы сделать ее палиндром в линейном времени.
Я могу только придумать решение O (N 2).
Может ли кто-нибудь помочь мне с решением O (N)?
Лучший ответ:
- Вернуть строку
- Используйте новый Knuth-Morris-Pratt, чтобы найти самое последнее совпадение (простейшая модификация – просто добавить исходную строку к возвращенному строка и игнорировать совпадения после len (строка).
- Добавим неповторимый остаток возвращаемой строки к оригиналу.
1 и 3, очевидно, линейны и 2 линейны, потому что Кнут-Моррис-Пратт есть.
Ответ №1Содержание
Если разрешено только добавление
A Scala решение:
def isPalindrome(s: String) = s.view.reverse == s.view def makePalindrome(s: String) = s + s.take((0 to s.length).find(i => isPalindrome(s.substring(i))).get).reverse
Если вам разрешено вставлять символы в любом месте
Каждый палиндром можно рассматривать как набор вложенных пар букв.
a n n a b o b | | | | | * | | — | | | ——— ——
Если длина палиндрома n четная, у нас будет n/2 пары. Если это нечетно, у нас будет n/2 полных пары и одна единственная буква в середине (пусть назовем это вырожденной парой).
Представьте их через пары индексов строк – левый индекс подсчитывается с левого конца строки, а правый индекс подсчитывается с правого конца строки, оба конца начинаются с индекса 0.
Теперь давайте напишем пары, начиная с внешнего и внутреннего. Итак, в нашем примере:
anna: (0, 0) (1, 1) bob: (0, 0) (1, 1)
Чтобы сделать любую строку палиндром, мы перейдем с обоих концов строки по одному символу за раз, и с каждым шагом мы в конечном итоге добавим символ для создания правильной пары одинаковых символов.
Пример:
Предположим, что входное слово “blob”
- Пара (0, 0) – (b, b) нормально, ничего не делать, эта пара в порядке. Позвольте увеличить счетчик.
- Пара (1, 1) есть (l, o). Не соответствует. Поэтому добавьте “o” в позицию 1 слева. Теперь наше слово стало “болбом”.
- Пара (2, 2). Нам не нужно смотреть даже на символы, потому что мы указываем на тот же индекс в строке. Готово.
Подождите, но у нас есть проблема: в пункте 2. мы произвольно решили добавить символ слева. Но мы могли бы добавить символ “l” справа. Это создало бы “blolb”, а также действительный палиндром. Так ли это важно? К сожалению, это происходит потому, что выбор в более ранних шагах может повлиять на количество пар, которые мы должны будем исправить, и, следовательно, сколько символов мы должны будем добавить в будущих шагах.
Легкий алгоритм: найдите все возможности. Это даст нам алгоритм O (2 ^ n).
Лучший алгоритм: используйте подход динамического программирования и обрезайте пространство поиска.
Чтобы упростить задачу, теперь мы отделяем вставку новых символов только от поиска правильной последовательности вложенных пар (от внешнего к внутреннему) и последующей фиксации их выравнивания. Итак, для слова “blob” у нас есть следующие возможности, как заканчивающиеся вырожденной парой:
(0, 0) (1, 2) (0, 0) (2, 1)
Чем больше таких пар мы найдем, тем меньше символов нам нужно будет добавить, чтобы исправить исходную строку. Каждая найденная полная пара дает нам два символа, которые мы можем использовать повторно. Каждая вырожденная пара дает нам один символ для повторного использования.
Основной цикл алгоритма будет итеративно оценивать парные последовательности таким образом, чтобы на шаге 1 были найдены все допустимые парные последовательности длины 1. Следующий шаг будет оценивать последовательности длины 2, третьи последовательности длины 3 и т.д. Когда на каком-то этапе мы не найдем возможностей, это означает, что предыдущий шаг содержит решение с наибольшим числом пар.
После каждого шага мы удалим парето-субоптимальные последовательности. Последовательность является субоптимальной по сравнению с другой последовательностью той же длины, если в ее последней паре доминирует последняя пара другой последовательности. Например. последовательность (0, 0) (1, 3) хуже, чем (0, 0) (1, 2). Последний дает нам больше места для поиска вложенных пар, и мы гарантированно найдем по крайней мере все пары, которые мы найдем для первого. Однако последовательность (0, 0) (1, 2) не хуже и не лучше (0, 0) (2, 1). Одна небольшая деталь, о которой мы должны остерегаться, состоит в том, что последовательность, заканчивающаяся вырожденной парой, всегда хуже, чем последовательность, заканчивающаяся полной парой.
После того, как все вместе:
def makePalindrome(str: String): String = { /** Finds the pareto-minimum subset of a set of points (here pair of indices). * Could be done in linear time, without sorting, but O(n log n) is not that bad 😉 */ def paretoMin(points: Iterable[(Int, Int)]): List[(Int, Int)] = { val sorted = points.toSeq.sortBy(identity) (List.empty[(Int, Int)] /: sorted) { (result, e) => if (result.isEmpty || e._2 <= result.head._2) e :: result else result } } /** Find all pairs directly nested within a given pair. * For performance reasons tries to not include suboptimal pairs (pairs nested in any of the pairs also in the result) * although it wouldn’t break anything as prune takes care of this. */ def pairs(left: Int, right: Int): Iterable[(Int, Int)] = { val builder = List.newBuilder[(Int, Int)] var rightMax = str.length for (i <- left until (str.length — right)) { rightMax = math.min(str.length — left, rightMax) val subPairs = for (j <- right until rightMax if str(i) == str(str.length — j — 1)) yield (i, j) subPairs.headOption match { case Some((a, b)) => rightMax = b; builder += ((a, b)) case None => } } builder.result() } /** Builds sequences of size n+1 from sequence of size n */ def extend(path: List[(Int, Int)]): Iterable[List[(Int, Int)]] = for (p <- pairs(path.head._1 + 1, path.head._2 + 1)) yield p :: path /** Whether full or degenerated. Full-pairs save us 2 characters, degenerated save us only 1. */ def isFullPair(pair: (Int, Int)) = pair._1 + pair._2 < str.length — 1 /** Removes pareto-suboptimal sequences */ def prune(sequences: List[List[(Int, Int)]]): List[List[(Int, Int)]] = { val allowedHeads = paretoMin(sequences.map(_.head)).toSet val containsFullPair = allowedHeads.exists(isFullPair) sequences.filter(s => allowedHeads.contains(s.head) && (isFullPair(s.head) || !containsFullPair)) } /** Dynamic-Programming step */ @tailrec def search(sequences: List[List[(Int, Int)]]): List[List[(Int, Int)]] = { val nextStage = prune(sequences.flatMap(extend)) nextStage match { case List() => sequences case x => search(nextStage) } } /** Converts a sequence of nested pairs to a palindrome */ def sequenceToString(sequence: List[(Int, Int)]): String = { val lStr = str val rStr = str.reverse val half = (for (List(start, end) <- sequence.reverse.sliding(2)) yield lStr.substring(start._1 + 1, end._1) + rStr.substring(start._2 + 1, end._2) + lStr(end._1)).mkString if (isFullPair(sequence.head)) half + half.reverse else half + half.reverse.substring(1) } sequenceToString(search(List(List((-1, -1)))).head) }
Примечание. Код не перечисляет все палиндромы, но дает только один пример, и гарантировано, что он имеет минимальную длину. Обычно существует больше палиндромов с одинаковой минимальной длиной (O (2 ^ n) наихудшего случая, поэтому вы, вероятно, не хотите перечислять их все).
Ответ №2#include<iostream> #include<string> using std::cout; using std::endl; using std::cin; int main() { std::string word, left(«»); cin >> word; size_t start, end; for (start = 0, end = word.length()-1; start < end; end—) { if (word[start] != word[end]) { left.append(word.begin()+end, 1 + word.begin()+end); continue; } left.append(word.begin()+start, 1 + word.begin()+start), start++; } cout << left << ( start == end ? std::string(word.begin()+end, 1 + word.begin()+end) : «» ) << std::string(left.rbegin(), left.rend()) << endl; return 0; }
Не знаю, добавляет ли он минимальное число, но производит палиндромы
Разъяснение:
- Мы начнем с обоих концов данной строки и проследуем внутрь к центру.
-
На каждой итерации мы проверяем, одинакова ли каждая буква, т.е. word[start] == word[end]?.
- Если они совпадают, мы добавляем копию переменной word[start] в другую строку под названием left, которая, как предполагается, будет использоваться в качестве левой стороны новой строки палиндрома, когда итерация завершена. Затем мы увеличиваем обе переменные (start) ++ и (end) – к центру
- В случае, если они не совпадают, мы добавляем копию переменной word[end] к той же строке left
-
И это основы алгоритма, пока цикл не будет выполнен.
-
Когда цикл закончен, выполняется последняя проверка, чтобы убедиться, что если мы получили палиндром нечетной длины, мы добавим средний символ к середине сформированного нового палиндрома.
Обратите внимание, что, если вы решите добавить oppoosite символы в строку left, обратное обо всем в коде станет истинным; то есть, какой индекс увеличивается на каждой итерации и который увеличивается, когда найдено совпадение, порядок печати палиндрома и т.д. Я не хочу повторять его снова, но вы можете попробовать его и увидеть.
Сложность выполнения этого кода должна быть O (N), предполагая, что метод добавления класса std::string выполняется в постоянное время.
Ответ №3
O (n).
Алгоритм:
Необходимо найти самый длинный палиндром в данной строке, содержащий последний символ. Затем добавьте все символы, которые не являются частью палиндрома, в обратную сторону строки в обратном порядке.
Ключевые моменты:
В этой задаче самый длинный палиндром в заданной строке ДОЛЖЕН содержать последний символ.
например:
вход: abacac
выход: abacacaba
Здесь самый длинный палиндром на входе, который содержит последнюю букву, – “cac”. Поэтому добавьте все буквы до “cac” на спину в обратном порядке, чтобы сделать всю строку палиндром.
написанный в С#, с несколькими зарегистрированными тестовыми примерами
static public void makePalindrome() { //string word = «aababaa»; //string word = «abacbaa»; //string word = «abcbd»; //string word = «abacac»; //string word = «aBxyxBxBxyxB»; //string word = «Malayal»; string word = «abccadac»; int j = word.Length — 1; int mark = j; bool found = false; for (int i = 0; i < j; i++) { char cI = word[i]; char cJ = word[j]; if (cI == cJ) { found = true; j—; if(mark > i) mark = i; } else { if (found) { found = false; i—; } j = word.Length — 1; mark = j; } } for (int i = mark-1; i >=0; i—) word += word[i]; Console.Write(word); } }
Обратите внимание, что этот код предоставит вам решение для наименьшего количества букв в APPEND TO BACK, чтобы сделать строку палиндром. Если вы хотите добавить к фронту, просто нужно сделать второй цикл, который идет в другую сторону. Это сделает алгоритм O (n) + O (n) = O (n). Если вам нужен способ вставить буквы в любом месте строки, чтобы сделать его палиндром, тогда этот код не будет работать для этого случая.
Ответ №4
Я считаю, что @Хронический ответ неверен, поскольку он, по-видимому, относится к лучшему сценарию, а не к худшему случаю, который используется для вычисления сложности большого вывода. Я приветствую доказательство, но “решение” фактически не описывает действительный ответ.
KMP находит совпадающую подстроку в O(n * 2k) времени, где n – длина входной строки и k подстрока, которую мы ищем, но не в O(n) указывает вам, что длинный палиндром во входной строке.
Чтобы решить эту проблему, нам нужно найти самый длинный палиндром в конце строки. Если этот длинный палиндром суффикса имеет длину x, минимальное количество добавляемых символов равно n — x. Например. строка aaba самая длинная суффиксная подстрока aba длины 3, поэтому наш ответ 1. Алгоритм, чтобы выяснить, является ли строка палиндром, занимает время O(n), используя KMP или более эффективный и простой алгоритм (O(n/2)):
Возьмите два указателя: один на первом символе и один на последнем символе
Сравните символы в указателях, если они равны, переместите каждый указатель внутрь, в противном случае верните false
Когда указатели указывают на один и тот же индекс (длина нечетной строки) или перекрываются (даже длина строки), верните true
Используя простой алгоритм, мы начинаем со всей строки и проверяем, является ли это палиндром. Если это так, вернем 0, а если нет, мы проверим строку string[1…end], string[2…end], пока не достигнем одного символа и не вернемся n — 1. Это приводит к времени выполнения O(n^2).
Разделение алгоритма KMP на
Таблица сборки
Искать длинный суффикс палиндрома
Построение таблицы занимает время O(n), а затем каждая проверка “вы являетесь палиндром” для каждой подстроки из string[0…end], string[1…end], …, string[end — 2…end], каждая занимает время O(n). k в этом случае является тем же самым фактором n, что простой алгоритм берет для проверки каждой подстроки, поскольку он начинается как k = n, затем проходит через k = n — 1, k = n — 2… точно так же, как и простой алгоритм.
TL; DR:
KMP может сказать вам, является ли строка палиндром в O(n) времени, но это дает ответ на вопрос, потому что вы должны проверить, являются ли все подстроки string[0…end], string[1…end], …, string[end — 2…end] палиндромами, что приводит к тому же (но на самом деле хуже ) runtime как простой алгоритм проверки палиндрома.
Ответ №5
Если кто-то хочет решить это в рубине, решение может быть очень простым
str = ‘xcbc’ # Any string that you want. arr1 = str.split(») arr2 = arr1.reverse count = 0 while(str != str.reverse) count += 1 arr1.insert(count-1, arr2[count-1]) str = arr1.join(») end puts str puts str.length — arr2.count Ответ №6
Я предполагаю, что вы не можете заменить или удалить существующие символы?
Хорошим началом было бы обратить вспять одну из строк и найти самую длинную общую подстроку (LCS) между инвертированной строкой и другой строкой. Поскольку это звучит так, это вопрос о домашнем задании или интервью, я оставлю все остальное вам.
Ответ №7
Здесь см. это решение
Это лучше, чем O (N ^ 2)
Проблема подразделяется на многие другие проблемы
например:
оригинальный “tostotor”
обратный “rototsot”
Здесь 2-я позиция – это “o”, поэтому разделение на две проблемы путем перехода на “t” и “ostot” из исходной строки
Для ‘t’: решение равно 1
Для “ostot”: решение равно 2, потому что LCS – это “tot” , и символы должны быть добавлены: “os”
Таким образом, сумма равна 2 + 1 = 3
def shortPalin( S): k=0 lis=len(S) for i in range(len(S)/2): if S[i]==S[lis-1-i]: k=k+1 else :break S=S[k:lis-k] lis=len(S) prev=0 w=len(S) tot=0 for i in range(len(S)): if i>=w: break; elif S[i]==S[lis-1-i]: tot=tot+lcs(S[prev:i]) prev=i w=lis-1-i tot=tot+lcs(S[prev:i]) return tot def lcs( S): if (len(S)==1): return 1 li=len(S) X=[0 for x in xrange(len(S)+1)] Y=[0 for l in xrange(len(S)+1)] for i in range(len(S)-1,-1,-1): for j in range(len(S)-1,-1,-1): if S[i]==S[li-1-j]: X[j]=1+Y[j+1] else: X[j]=max(Y[j],X[j+1]) Y=X return li-X[0] print shortPalin(«tostotor»)
