Палиндром при удалении символов

Question

Линейный тип данных называется палиндромом, если он читается одинаково справа налево, например, слово «babab». Написать код который считает минимальное количество символов,при удалении которых строка становится палиндромом

Поможете решить задачу?получается она сложная походу для всех нас ))

function solution(x){
    var pat = 0
    if (x === x.split("").reverse().join("")) {return pat}
    for (var i = 0; i < x.length; i++) {
        for (var j = x.length-1; j > i; j--) {
            if (x[i]==x[j]) {
                pat = i + x.length-1 - j
                x = x.substring(i+1,j)
                if (x === x.split("").reverse().join("")) {return pat}
            }
        }
    }
    for (var i = 0; i < x.length; i++) {
        for (var j = x.length-1; j > i; j--) {
            if (x[i]==x[j]) {
                pat = i + x.length-1 - j
                x = x.substring(i+1,j)
                if (x === x.split("").reverse().join("")) {return pat}
            } else {
                pat++
                x = x.slice(1)
            }
        }
    }
    if (x.length==1 || x.length==0 || x.length==2) {
        return pat
    }
}

console.log(solution("wanna")) //1
console.log(solution("anna")) //0
console.log(solution("qaxaqax")) //2
console.log(solution("aebcbda")) //2

Она не идеальная,а если например там не 2 а 3 элементы? )) не написать же 3 цикла

Answer 1

Заранее один раз проверяем, не является ли строка палиндромом. Если так, то ничего делать не надо и сразу возвращаем лучший вариант - 0 замен.

Иначе начинаем увеличивать число замен и проверять каждый вариант отдельно. С единицы до длины строки минус 2 т.к. "длина строки минус 1" - это просто удаление всех символов кроме одного и такой вариант мы вернём в самом конце как единственно возможный.

Для каждой итерации находим все возможные комбинации индексов в строке, которые можно удалить и получить таким образом уникальные строки поменьше.

Перебираем эти варианты индексов. Для каждой пачки перебираем сами индексы. Удаляем символы из строки по ним (обязательно с конца к началу, чтобы индексы в конце строки "не поехали"). Затем проверяем результат и принимаем решение.

function solution(S) {
  const isPoly = s => s.join("") === s.reverse().join("");

  const idx = (from, to, size) => {
    let res = [];
    if (size) {
      for (let i = from; i <= to - (size - 1); i++) {
        let el = [i];
        if (size > 1) {
          let additional = idx(i + 1, to, size - 1);
          for (let a = 0; a < additional.length; a++) {
            res.push(el.concat(additional[a]));
          }
        } else {
          res.push(el);
        }
      }
    }
    return res;
  };
  
  if (isPoly(S.split(""))) {
    return 0;
  }

  for (let rm = 1; rm < S.length - 1; rm++) {
    let rmIdx = idx(0, S.length - 1, rm);
    for (let a = 0; a < rmIdx.length; a++) {
      let A = rmIdx[a];
      let s = S.split("");
      for (let i = A.length - 1; i >= 0; i--) {
        s.splice(A[i], 1);
        if (isPoly(s)) {
            return rm;
        }
      }
    }
  }

  return S.length - 1;
}

console.log("wanna -> _anna (1): " + solution("wanna"));
console.log("anna -> anna (0): " + solution("anna"));
console.log("qaxaqax -> qaxaq__ (2): " + solution("qaxaqax"));
console.log("aebcbda -> a_bcb_a (2): " + solution("aebcbda"));
console.log("abcdfedcba -> abcd_edcba (1): " + solution("abcdfedcba"));

Итого:

wanna -> _anna (1): 1
anna -> anna (0): 0
qaxaqax -> qaxaq__ (2): 2
aebcbda -> a_bcb_a (2): 2
abcdfedcba -> abcd_edcba (1): 1

Answer 2

Эту задачу можно решить с помощью динамического программирования. Заводится таблица NxN (N=len(s)), в ячейках A[l,r] которой будут содержаться наибольшие длины палиндромных подпоследовательностей подстроки, начинающейся в позиции l и кончающейся в позиции r.

Понятно, что диагональ заполняется единицами (односимвольная подстрока есть палиндром).

Потом проверяем:

если r-l=1, то A[l,r] = 1 или 2 в зависимости от равенства символов

если s[l] не равно s[r], то A[l,r] есть максимум из результатов для укороченных слева и справа подстрок

 A[l, r] = max(A[l+1,r], A[l, r-1])

а если равно, то к выбору добавляется ещё один член, т.к. совпадающие символы справа и слева образуют палиндром с любым внутренним палиндромом

 A[l, r] = max(A[l+1,r], A[l, r-1], A[l+1,r-1]+2)

Answer 3

Решил с помощью @Lexx918

function solution(str){
    var n = str.length
    var L = []
    for (let i = 0; i < n; i++){
        let tox = []
        L.push(tox)
        L[i][i] = 1
    }
    for (let cl = 2; cl <= n; cl++){
        for ( let i = 0;i < n - cl + 1;i++){
            var j = i + cl - 1
            if (str[i] == str[j] && cl == 2){
                L[i][j] = 2
            }
            else if (str[i] == str[j]){
                L[i][j] = L[i + 1][j - 1] + 2
            }
            else{
                L[i][j] = Math.max(L[i][j - 1],L[i + 1][j])
            }
        }
    }
    return n - L[0][n - 1]
}

console.log(solution("wanna"),"wanna") //1
console.log(solution("anna"),"anna") //0
console.log(solution("qaxaqax"),"qaxaqax") //2
console.log(solution("aebcbda"),"aebcbda") //2
console.log(solution("abcdeak"),"abcdeak") //4
console.log(solution("abcdfedcba"),"abcdfedcba") //1
console.log(solution("abcdedcba"),"abcdedcba") //0
console.log(solution("aeccbda"),"aeccbda") //3
console.log(solution("abbca"),"abbca") //1
console.log(solution("wa"),"wa") //1
console.log(solution("badba"),"badba") //2
console.log(solution(" "),"") //0
console.log(solution("010000"),"010000") //1
console.log(solution("010100"),"010100") //1
console.log(solution("011100"),"011100") //1
console.log(solution("010140"),"010140") //1
console.log(solution("015140"),"015140") //1
console.log(solution("011100011000"),"011100011000") //3
console.log(solution("bbaaaba"),"bbaaaba") //2

Answer 4

Вот решение с помощью рекурсии)

function solution(input){
    function rec(a, b){
        if(a >= b) 
            return 0;

        if(input[a] == input[b])
            return rec(a + 1, b - 1);

        return Math.min(rec(a + 1, b), rec(a, b - 1)) + 1;
    }

    return rec(0, input.length - 1);
}

console.log(solution("wanna"),"wanna") //1
console.log(solution("anna"),"anna") //0
console.log(solution("qaxaqax"),"qaxaqax") //2
console.log(solution("aebcbda"),"aebcbda") //2
console.log(solution("abcdeak"),"abcdeak") //4
console.log(solution("abcdfedcba"),"abcdfedcba") //1
console.log(solution("abcdedcba"),"abcdedcba") //0
console.log(solution("aeccbda"),"aeccbda") //3
console.log(solution("abbca"),"abbca") //1
console.log(solution("wa"),"wa") //1
console.log(solution("badba"),"badba") //2
console.log(solution(" "),"") //0
console.log(solution("010000"),"010000") //1
console.log(solution("010100"),"010100") //1
console.log(solution("011100"),"011100") //1
console.log(solution("010140"),"010140") //1
console.log(solution("015140"),"015140") //1
console.log(solution("011100011000"),"011100011000") //3
console.log(solution("bbaaaba"),"bbaaaba") //2

БЛОГ НА HUSL

Палиндром при удалении символов

Ответы (4 шт):