4

Линейный тип данных называется палиндромом, если он читается одинаково справа налево, например, слово «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 цикла

14
  • 2
    рекурсия (7 символов нужно...)
    – user176262
    18 июн 2020 в 12:42
  • что дальше?что поменять?
    – ROBB STARK
    18 июн 2020 в 13:05
  • Поменять код, сделав вызовы функции solution рекурсивными, и передавать туда в цикле текущую строку без одной буквы, пока не получится палиндром или не останется одна буква (это считается палиндромом?).
    – user176262
    18 июн 2020 в 13:08
  • ну одна буква считается палиндромом подумать надо как решить
    – ROBB STARK
    18 июн 2020 в 13:12
  • "подумать надо как решить" - +1
    – user176262
    18 июн 2020 в 13:13

4 ответа 4

0

Заранее один раз проверяем, не является ли строка палиндромом. Если так, то ничего делать не надо и сразу возвращаем лучший вариант - 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
8
  • А сработает на abcdfedcba ?
    – MBo
    18 июн 2020 в 15:13
  • Неправильно. Символы могут удаляться из середины. aebcbda - 2 (e и d)
    – user176262
    18 июн 2020 в 15:13
  • Мне показалось условие - удалять с краёв. Можно и из центра. Секунду..
    – Lexx918
    18 июн 2020 в 15:16
  • @Lexx918 вариант был хорошим,я с начала тож думал что можно убирая с краев получить ответ,но нет. Вариантов тут много но ни одна не идет к ответу
    – ROBB STARK
    18 июн 2020 в 16:13
  • 1
    скорее всего не влезает в ограничения по ресурсам. попробуйте реализовать готовые алгоритмы. благо они есть в сети: espressocode.top/… или espressocode.top/…
    – Lexx918
    19 июн 2020 в 6:47
0

Эту задачу можно решить с помощью динамического программирования. Заводится таблица 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)
4
  • 1
    такое ощущение что тут про поиск максимального палиндрома в строке, а не про то, как его найти удалив каике-либо символы из строки.
    – teran
    18 июн 2020 в 16:39
  • @teran Не-не, тут как раз можно пропускать ненужные символы, а в обычной задаче про поиск максимального палиндрома он должен быть непрерывным. Т.е. составили палиндромчик из середины строки, а потом можно его нарастить не соседними символами.
    – MBo
    18 июн 2020 в 16:51
  • @MBo может с кодом поможешь? увидим
    – ROBB STARK
    18 июн 2020 в 18:05
  • Нет, код писать не буду, на JS я прилично не сделаю. Описание принципа важнее, тем более, что оно подробное и без намёков.
    – MBo
    19 июн 2020 в 4:11
0

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

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

-1

Решил с помощью @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

1
  • Т.е. что я вчера написал - можно было не читать и не вдаваться ;)
    – MBo
    19 июн 2020 в 11:19

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.