Конвертировать строку в палиндром с наименьшим количеством вставок - PullRequest
Новая
       53

Конвертировать строку в палиндром с наименьшим количеством вставок

2 голосов
/ 15 марта 2019

Это вопрос от https://www.dailycodingproblem.com/:

По заданной строке найдите палиндром, который можно сделать, вставив наименьшее количество символов в любом месте слова.Если имеется более одного палиндрома минимальной длины, который можно сделать, верните лексикографически самый ранний (первый в алфавитном порядке).

Например, для строки «race» вы должны вернуть «ecarace»,так как мы можем добавить к нему три буквы (это наименьшая сумма для создания палиндрома).Есть семь других палиндромов, которые можно сделать из «расы», добавив три буквы, но «ecarace» идет первым по алфавиту.

В качестве другого примера, учитывая строку «google», вы должны вернуть «elgoogle».

Это похоже на этот ТАК вопрос или этот пост GeeksforGeeks.Похожи, но не одинаковы;ни один из них не дает никакого объяснения рецидива, как будто они вытащили раствор из воздуха, и они не восстанавливают решение, не говоря уже о лексикографически самом раннем.

После некоторых размышлений мое пониманиеследующим образом:

Обратите внимание, что для любой строки s[i..j], если s[i] == s[j], то число вставок, необходимых для ее палиндрома, равно числу вставок, необходимых для s[i+1..j-1] палиндром.

Если, однако, s[i] != s[j], то мы можем преобразовать s[i..j-1] в палиндром и затем вставить s[j] в начале, или преобразовать s[i+1..j] в палиндром и вставить s[i] в конце.Так как мы ищем наименьшее количество вставок, мы выберем минимум из двух вариантов.Количество вставок на единицу больше количества вставок, необходимого для выбранной подзадачи (для добавления символа в начале или в конце).

Как восстановить лексикографически раннее решение?

Ответы [ 2 ]

2 голосов
/ 15 марта 2019

Сначала давайте ответим «как мне восстановить решение», а затем сосредоточимся на заказе.Предполагая, что вы сохраняете количество вставок в двумерной матрице insertions[start][stop], вам просто нужно пересмотреть ваши шаги, «собирая» символы, вставленные по ходу.Нам понадобится новый массив для хранения выходной строки, длина которого равна нашей стартовой строке плюс минимальное количество вставок.Мы также сохраним два индекса, указывающих на следующие доступные точки спереди и сзади в массиве.

Начнем с сравнения первой и последней букв текущей подстроки и, если они равны, присваивают выходную строку обоимиз них, в следующих доступных позициях спереди и сзади соответственно.Например, если у нас есть FYRF в качестве текущей подстроки, мы назначим нашу выходную строку F..F, где . - неопределенные символы.Тогда наша подстрока становится s[i+1..j-1] или YR.

Если два символа не совпадают, мы сравним наши записи в insertions[i+1][j] и insertions[i][j-1], чтобы увидеть, какие из них меньше (хотя бы одиниз них будет ровно на один меньше insertions[i][j]).Если они равны, просто выберите один (мы вернемся к этому позже).Назначьте символ в нашей выходной строке, который соответствует букве подстроки, которую мы продублировали / вставили, при следующих доступных передних и задних индексах в выходной строке.То есть в случае JLL, если мы решим добавить J для JLLJ, мы возьмем подстроку s[i+1..j], поэтому мы сохраним J и J в нашей выходной строкеJ..J.Если бы наша выходная строка уже содержала AR....RA, мы бы вместо этого сохранили ARJ..JRA.Мы повторяем весь этот процесс до тех пор, пока не будут назначены все символы.

Теперь, чтобы упорядочить его лексикографически.Что касается случая в предыдущем абзаце, где insertions[i+1][j] и insertions[i][j-1] равны, мы не должны выбирать один из них случайным образом.Вместо этого мы должны сравнить s[i] и s[i+1] лексикографически, и если s[i] идет первым, вставить s[i] в строку вывода / продолжить на insertions[i+1][j].В противном случае используйте s[i+1] / insertions[i][j-1].Это даст нам лексикографически самую раннюю строку из всех доступных вариантов.

1 голос
/ 15 марта 2019

ОП здесь: @ dillon-davis 'ответ правильный (upvoted), хотя я сам к этому уже разобрался.Я уже предоставил объяснение основного алгоритма в вопросе, @ dillon-davis предоставил объяснение реконструкции, вот рабочий код в Scala для полноты. 

def makePalindromeByFewestEdits(word: String): String = {
    val n = word.length
    val dp = Array.ofDim[Int](n, n)

    for (window <- 1 until n)
      (0 until n)
        .map(start => (start, start + window))
        .takeWhile(_._2 < n)
        .foreach {
          case (start, end) if word(start) == word(end) =>
            dp(start)(end) = dp(start + 1)(end - 1)
          case (start, end) =>
            dp(start)(end) = math.min(dp(start + 1)(end), dp(start)(end - 1)) + 1
        }

    val minInsertions = dp(0)(n - 1)
    val palindrome = Array.ofDim[Char](n + minInsertions)

    @tailrec
    def reconstruct(start: Int, end: Int, count: Int, offset: Int): String = {
      if (count == 0) {
        // we have written 'start' characters from the beginning, the current insertion index is 'offset', and
        // the number of characters left to be written are the substring word[start..end]
        Array.copy(word.toCharArray, start, palindrome, offset, end - start + 1)
        palindrome.mkString
      } else {
        val (s, e, c, ch) = if (word(start) == word(end))
          (start + 1, end - 1, count, word(start))
        else if (dp(start + 1)(end) < dp(start)(end - 1) ||
          (dp(start + 1)(end) == dp(start)(end - 1) && word(start) < word(end))
        )
          (start + 1, end, count - 1, word(start))
        else
          (start, end - 1, count - 1, word(end))

        palindrome(offset) = ch
        palindrome(palindrome.length - 1 - offset) = ch
        reconstruct(s, e, c, offset + 1)
      }
    }

    reconstruct(0, n - 1, minInsertions, 0)
}
...