Сложный палиндром

115

21 марта 2021, 12:00

Дана строка. Из данной строки необходимо сделать палиндром следующим образом:

Необходимо сделать из данной строки палиндром минимально возможной длины.

Например: abcb -> abcba, aaa -> aaa, a -> a, abcded -> abcdedcba, 123432 -> 1234321, lollipop -> lollipopillol, uguutu -> uguutuugu, abcdefghijkjihgfe -> abcdefghijkjihgfedcba.

Принцип образования сложного палиндрома я понял так: например, у нас есть строка abcded. Сразу ее переворачиваем в dedcba. Находим одинаковую часть у этих двух строк - ded. Вычитаем из второй строки dedcba общую часть ded. Первая срока abcded и остаток второй строки cba образуют кратчайший палиндром - abcdedcba.

Набросал код, и он даже проходит несколько первых тестов, но потом валится на более сложных... Помогите сделать так чтобы он работал на всех тестах корректно.

    public static void main(String[] args) throws IOException {
    Scanner in = new Scanner(System.in);
    String s = in.next();
    char[] charArray = s.toCharArray();
    ArrayList<Character> list = new ArrayList<Character>();
    for (char ch : charArray)
        list.add(ch);
    for (int i = charArray.length - 1; i >= 2; i--) {
        if (charArray[i] != charArray[i - 2])
            list.add(charArray[i - 2]);
    }
    for (char ch : list) {
        System.out.print(ch);
    }
    in.close();
}

Answer 1

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        String sourceString = new Scanner(System.in).nextLine();
        StringBuilder sb = new StringBuilder(sourceString.substring(0, getSubstringIndex(sourceString)));
        sb.reverse();
        sb.insert(0, sourceString);        
        System.out.println(sb.toString());
    }
    public static int getSubstringIndex(String source) {        
        char[] chArray = source.toCharArray();
        int count = chArray.length - 1;
        for (int i = 0; i < chArray.length; i++) {
            if (chArray[i] == chArray[count]) count--;
            else {
                count = chArray.length - 1;
                if (chArray[i] == chArray[count]) count--;
            }            
        }        
        return ++count;        
    }
}

Answer 2

Вот мой вариант решения:

int iCount = sbSrcStr.length();
// проверяем, равна ли получившаяся
// строка точно такой же только реверсивной
for (int i = 0; i < iCount; i++) {
    if (sbSrcStr.toString().equals(sbSrcStr.reverse().toString()))
        break;
    else
        sbSrcStr.reverse();
    sbSrcStr.insert(iCount, sbSrcStr.substring(i, i+1));
}
System.out.println(sbSrcStr.toString());