Как преобразовать строку в палиндром с минимальным количеством замен символов, чтобы в строке палиндромов было заданное слово?

Question

У нас есть строка s, содержащий строчные буквы алфавита (az). Мы можем заменить любой символ любым другим символом, и мы можем сделать это любое количество раз.

Мы можем сделать палиндромную строку p от sтак, что p содержит заданные конкретные слова (т.е. давайте предположим, linkedin). Теперь нам нужно найти наименьшее количество вставок, которое потребуется для преобразования строки s в p,

бывший - s знак равно linkedinininininтогда строка палиндрома p было бы linkedinnideknil и результат будет 6.

второй пример (чтобы было понятнее) - s знак равно linkaeiouideknilзатем p знак равно linkedinnideknil и результат будет для 4, потому что мы заменим a с e, e с d, o а также u с n,

Я попытался решить ее, взяв LCS из s и p и вычтя это из длины s. но проблема в том, как мне убедиться, что палиндром гарантированно содержит данное слово (Linkedin)?

Пожалуйста, предоставьте ваш подход. Благодарю.

Answer 1

Я бы итерировал строку и палиндром одновременно; вставка символов, которые не существуют во входной строке, и замена подстрок при появлении следующего доступного символа:

public int palindromify(String pal, String read) {
    StringBuilder sb = new StringBuilder(read);
    int insertions = 0; //track insertions
    int palIndex = 0; //our progress through the palindrome
    //caches characters we know aren't further in the input, saves time
    Set<Character> none = new HashSet<>();
    boolean outOfInput = false;
    for (int i = 0;; i++) {
        if (i >= sb.length()) {
            outOfInput = true; //if we run out of input, we know we have to append remainder
            break;
        }
        if (palIndex >= pal.length()) {
            sb.delete(i, sb.length()); //remove remainder, we're out of palindrome
            break;
        }
        char curr = pal.charAt(palIndex++); //increment palindrome
        if (sb.charAt(i) != curr) {
            //perform lookahead
            boolean found = false;
            if (!none.contains(curr)) { //only search a missing char once
                for (int w = i + 1; w < sb.length(); w++) {
                    if (sb.charAt(w) == curr) {
                        sb.replace(i, w + 1, "" + curr); //replace up to our lookahead
                        found = true;
                        break;
                    }
                }
                if (!found) {
                    none.add(curr);
                }
            }
            if (!found) {
                //simply insert our character, later ones are useful for others
                sb.insert(i, curr);
                insertions++; //this was an insertion, one of our counted values
            }
        }
    }
    //if we ran out of input, append the rest of palindrome
    return insertions + (outOfInput ? pal.length() - sb.length() : 0);
}

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

Таким образом, при звонке:

palindromify("linkedinnideknil", "linkedinininin"); //prints '4'

Создать настоящий палиндром довольно легко, и гораздо меньше работы:

String s = /* some value */;
s += new StringBuilder(s).reverse();

Редактировать: не работает для некоторых крайних случаев, исправление.

Answer 2

Если я правильно понял твой вопрос,

Вы можете создать палиндром, а затем заменить неправильные буквы в s:

String s="linkaeiouideknil";
String p="";
String word="linkedin";
char[] wordC = word.toCharArray();
StringBuilder sb = new StringBuilder();
sb.append(word);
String drow = sb.reverse().toString();
sb.reverse();
sb.append(drow);
String pali=sb.toString();
char[] sC = s.toCharArray();
sC=Arrays.copyOf(sC, pali.length());
sb.delete(0, sb.length());
int counter=0;
for (int i = 0; i < sC.length; i++) {
    if(sC[i]!=pali.charAt(i)){
        sC[i]=pali.charAt(i);
        counter++;
    }
    sb.append(sC[i]);
}
System.out.println(counter);    
p=sb.toString();
System.out.println(p);

выход при запуске 4.

Answer 3

Сначала я бы создал палиндром, в который вы хотите преобразовать вашу строку. Затем вычислите расстояние редактирования от вашей исходной строки до созданного вами палиндрома, где ваши правки заменяют символы в строке: без вставок и удалений. Код будет выглядеть примерно так

def minReplacements(original, palindrome, m, n):
    # base case:  we're finished processing either string so we're done
    if (m == 0 or n == 0):
        return 0

    # The characters in the string match so find out how many replacements are
    # required for the remaining characters in the strings.
    if (original[m-1] == palindrome[n-1]):
        return minReplacements(origininal, palindrome, m-1, n-1)

    # Recurse on replacing a character in the original string
    # with a character in the palindrome string
    return 1 + minReplacements(origininal, palindrome, m-1, n-1)

Если, с другой стороны, вы хотите узнать, сколько замен символов, вставок или удалений необходимо для преобразования исходной строки в строку палиндрома, измените последнюю строку кода выше с помощью этого кода:

    return 1 + min(minReplacements(origininal, palindrome, m, n-1),   # insert character
                   minReplacements(origininal, palindrome, m-1, n-1), # replace character
                   minReplacements(origininal, palindrome, m-1, n))   # delete character

Код тогда выглядит так:

def minReplacements(original, palindrome, m, n):
    # base case:  we're finished processing either string so we're done
    if (m == 0):  # done processing original string
        return n  # return the number of characters left in palindrome
    if (n == 0):  # done processing palindrome
        return m  # return the number of characters left in the original string

    # The characters in the string match so find out how many edits are
    # required for the remaining characters in the strings.
    if (original[m] == palindrome[n]):
        return minReplacements(origininal, palindrome, m-1, n-1)

    # Recurse on editing a character in the original string
    # with a character in the palindrome string
    return 1 + min(minReplacements(origininal, palindrome, m, n-1),   # insert character
                   minReplacements(origininal, palindrome, m-1, n-1), # replace character
                   minReplacements(origininal, palindrome, m-1, n))   # delete character