Проблема с нарезкой в рекурсии javascript

#javascript #recursion #palindrome

Вопрос:

все! Я знаю, что это не лучший возможный базовый вариант для рекурсии, и я знаю, что в нем есть недостатки. Но, работая над этим, я понял, что несколько раз он пропускает нарезку первого элемента массива, в конечном итоге возвращая false вместо true . Возможно, я что-то упускаю, но мне бы хотелось узнать, почему это происходит?

пс. Я приношу извинения, если этот вопрос может быть сформулирован не совсем точно, но я надеюсь, что код даст вам какое-то лучшее представление.

Код:

 function palindrome(string) {
  let str = string.replace(/[^A-Za-z0-9]/g, '')
  console.log( str )
  str = str.split("")
  if (str.length === 3 amp;amp; str[0] === str[2] || str.length === 1) {
    return true
  } else if (str.length === 2 amp;amp; str[0] !== str[1]) {
    return false
  } else {
    return palindrome(string.slice(1, -1))
  }
  return false
}
console.log(palindrome("Anne I vote more cars race Rome to Vienna"))

С возвращаемым значением:

 ['A', 'n', 'n', 'a', 'I', 'v', 'o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e', 't', 'o', 'V', 'i', 'e', 'n', 'n', 'a']
['n', 'n', 'a', 'I', 'v', 'o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e', 't', 'o', 'V', 'i', 'e', 'n', 'n']
['n', 'a', 'I', 'v', 'o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e', 't', 'o', 'V', 'i', 'e', 'n']
['a', 'I', 'v', 'o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e', 't', 'o', 'V', 'i', 'e']
['I', 'v', 'o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e', 't', 'o', 'V', 'i']
['I', 'v', 'o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e', 't', 'o', 'V']
['I', 'v', 'o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e', 't', 'o']
['v', 'o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e', 't', 'o']
['v', 'o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e', 't']
['o', 't', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e']
['t', 'e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm', 'e']
['e', 'm', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o', 'm']
['m', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R', 'o']
['m', 'o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e', 'R']
['o', 'r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e']
['r', 'e', 'c', 'a', 'r', 's', 'r', 'a', 'c', 'e']
['e', 'c', 'a', 'r', 's', 'r', 'a', 'c']
['c', 'a', 'r', 's', 'r', 'a']
['c', 'a', 'r', 's', 'r']
['a', 'r', 's']
['r', 's']
false

1. Этот вывод не из примера, который вы показываете.

2. Вам нужно проверить, совпадают ли первый и последний символы, прежде чем выполнять рекурсию.

3. Разве это не должно быть «Анна, я голосую за то, чтобы больше автомобилей мчалось из Рима в Вену»?

4. Вы также внимательно сравниваете случай. Вам нужно преобразовать строку в один регистр.

5. Обратите внимание , что вы вызываете slice string , а не str , поэтому он включает пробелы и любые другие символы, не являющиеся словами. Я предлагаю использовать str.join('') вместо string .

Ответ №1:

Проблемы с реализацией

Я боюсь, что с этой реализацией есть по крайней мере три отдельные проблемы.

Во-первых, он забывает указывать символы в одном и том же регистре, и начальный заглавный 'A' от 'Anne' не будет соответствовать окончательному строчному 'a' от 'Vienna' .

Во-вторых, он правильно изменяет string ввод, чтобы удалить не буквенно-цифровые символы, но затем, когда он повторяется, он делает это на этом оригинале string , а не на новом str .

В-третьих, и это самое главное, он не проверяет самый важный факт, прежде чем он повторится: он не проверяет, соответствует ли первый символ последнему символу.

Работа с начальной версией

Мы можем исправить все это и получить версию, которая выглядит следующим образом:

 function palindrome(string) {
  let str = string.replace(/[^A-Za-z0-9]/g, '') .toLowerCase ().split("") // Issue 1 -- case
  // console.log( str.join('') )
  if (str.length === 3 amp;amp; str[0] === str[2] || str.length === 1) {
    return true
  } else if (str.length === 2 amp;amp; str[0] !== str[1]) { // Issue 3 -- compare first and last
    return false
  } else if (str [0] !== str [str .length - 1]) {
    return false
  } else {
    return palindrome(str.slice(1, -1).join('')) // Issue 2 -- recur on correct item
  }
  return false
}

console .log (palindrome ("Anne I vote more cars race Rome to Vienna"))   //=> true
console .log (palindrome ("Anne I vote more cars X race Rome to Vienna")) //=> false
console .log (palindrome ("A man, a plan, a canal: Panama!"))             //=> true
console .log (palindrome ("A man, a plan, a banal palindrome."))          //=> false

Remaining problems

Но даже здесь есть какое-то настоящее уродство. Мы преобразуем туда и обратно строки и массивы при каждом вызове. Мы запускаем очистку строки при каждом вызове, когда она не должна быть нужна после первого. И в нем содержится гораздо больше отдельных случаев, чем действительно необходимо.

Не продолжайте конвертировать

Первое исправление тривиально. Нам просто не нужны массивы здесь. Мы можем провести все наши тесты на струнах. Символы в строке могут быть проиндексированы точно так же, как элементы массива, и они обладают эквивалентным length свойством.

Инициализировать только один раз

Вторая проблема, связанная с повторным запуском инициализации при каждом вызове, обычно решается одним из двух способов: добавлением дополнительных параметров, которые по умолчанию используются при первоначальном вызове, или добавлением вспомогательных функций. Мы выберем последнее, потому что с первым есть некоторые реальные потенциальные проблемы (хотя это все еще достаточно часто стоит рассмотреть). Это разбивается на два стиля. Мы можем вложить вспомогательную функцию в нашу основную функцию, а затем вызвать ее изнутри. Или мы можем сделать это внешней функцией, которую мы просто вызываем. Ответ от MisterJoJo удачно демонстрирует первый стиль, поэтому мы можем взглянуть на второй. Здесь мы можем написать внутреннюю рекурсивную _isPalindrome функцию, которая принимает строку буквенно-цифровых символов в нижнем регистре и возвращает логическое значение. А затем мы могли бы написать общедоступную функцию-оболочку, которая принимает любую строку, нормализует ее, удаляя все не буквенно-цифровые символы и заключая ее в нижнюю оболочку, передавая результат этой внутренней функции и возвращая ее результат. Это может выглядеть примерно так ¹:

 const isPalindrome = (string) =>
  _isPalindrome (string .replace (/W/g, '') .toLowerCase())

const _isPalindrome = (cs) => /* ... recursive version here ... */

В наши дни простых в использовании модулей JS эта внутренняя функция может быть инкапсулирована в модуль, оставляя общедоступной только основную функцию.

Обрабатывайте меньше дел

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

Для рекурсивной функции нам нужен по крайней мере один базовый случай. Когда мы больше не можем проверять, совпадают ли первый и последний символ? Ответ довольно ясен: когда у нас нет отдельных первого и последнего символов.². Таким образом, наш базовый случай-это когда в строке ноль или один символ. Строка из одного символа явно является палиндромом. Так же как и строка из нулевых символов; если это звучит странно, пожалуйста, найдите пустые истины. Итак, теперь у нас есть простой базовый случай и простой рекурсивный случай, и мы можем просто написать нашу функцию:

 const isPalindrome = (string) => 
  _isPalindrome (string .replace (/W/g, '') .toLowerCase ())

const _isPalindrome = (cs) => 
  cs .length < 2 
    ? true 
    : cs [0] == cs [cs .length - 1] amp;amp; _isPalindrome (cs .slice (1, -1))

console .log (isPalindrome ("Anne I vote more cars race Rome to Vienna"))   //=> true
console .log (isPalindrome ("Anne I vote more cars X race Rome to Vienna")) //=> false
console .log (isPalindrome ("A man, a plan, a canal: Panama!"))             //=> true
console .log (isPalindrome ("A man, a plan, a banal palindrome."))          //=> false

Использование служебных функций

Мы легко могли бы остановиться здесь. Но в этом коде все еще есть некоторое уродство. Все манипуляции с индексами требуют некоторого чтения, чтобы понять. Есть веский аргумент в пользу того, чтобы перенести это уродство в хорошо названные вспомогательные функции. У меня обычно есть помощники last и first ³, и достаточно легко также написать a middle . Они принимают первые или последние символы строки или массива, или, например middle , принимают все, что находится между первым и последним символами. Их использование может сделать нашу основную функцию более читаемой:

 const first = (xs) => xs [0]
const last = (xs) => xs [xs .length - 1]
const middle = (xs) => xs .slice (1, -1)

const isPalindrome = (string) => 
  _isPalindrome (string .replace (/W/g, '') .toLowerCase ())

const _isPalindrome = (cs) => 
  cs .length < 2 
    ? true 
    : first (cs) == last (cs) amp;amp; _isPalindrome (middle (cs))

Общая обработка

Мы случайно написали более общую версию функции, чем мы пытались написать! Обратите внимание, что мы можем использовать эту же внутреннюю функцию для массивов:

 _isPalindrome (['foo', 'bar', 'qux', 'bar', 'foo']) //=> true
_isPalindrome (['foo', 'bar', 'qux', 'foo'])        //=> false

Семантика проста. Массив является палиндромом, если в нем меньше двух элементов или если первый и последний элементы одинаковы, а остальные элементы образуют палиндром.

В основном это была счастливая случайность. Когда я заметил это, я изменил имя параметра, которое я первоначально написал , letters на более общее cs , которое просто может прийти на ум characters , но не настаивает на этом.

Отмечая общий характер этой реализации, я бы, вероятно, изменил middle ее, чтобы мы могли перенести это на еще большее количество типов, на любой конечный итеративный тип. middle не буду заниматься этим прямо сейчас, потому что не у всех таких итераций есть slice методы. Но все они ⁴ могут быть преобразованы в массивы, и тогда мы можем использовать метод массива slice .

Вот простое обновление middle , чтобы сделать эту функцию еще более универсальной:

 const middle = (xs) => [...xs] .slice (1, -1)

Как я уже сказал, это была счастливая случайность. Я не заметил этого во время написания кода, только когда набирал этот пост.

Гораздо проще `isPalindrome`

Наконец, в вопросе отмечалось, что эта проблема, вероятно, не лучше всего решается с помощью рекурсии. Это совершенно верно. Мы уже упоминали об этом раньше, но упоминали, что строка является палиндромом, если она читается одинаково вперед и назад. Мы можем написать это напрямую:

 const isPalindrome = (string) => 
  _isPalindrome (string .replace (/W/g, '') .toLowerCase ())

const _isPalindrome = (s) => 
  s == s .split ('') .reverse () .join ('')

console .log (isPalindrome ("Anne I vote more cars race Rome to Vienna"))   //=> true
console .log (isPalindrome ("Anne I vote more cars X race Rome to Vienna")) //=> false
console .log (isPalindrome ("A man, a plan, a canal: Panama!"))             //=> true
console .log (isPalindrome ("A man, a plan, a banal palindrome."))          //=> false

Хотя String у нас нет reverse метода, мы можем легко преобразовать его в массив, перевернуть массив и объединить результат обратно в строку. Затем мы просто проверяем, совпадает ли перевернутая строка с исходной.⁵

Эта версия не является универсальной, как предыдущая, но она определенно является более прямым переводом идеи палиндрома непосредственно в код.

¹ Обратите внимание, что регулярное выражение /W/g в точности эквивалентно /[^A-Za-z0-9]/g . Это обратная w сторона , которая представляет [a-zA-z0-9] , но ее проще печатать.

² Мы также можем отметить, что если первый и последний символы совпадают, то есть если наша строка имеет длину всего один символ, мы могли бы использовать один и тот же процесс. Все, что изменится, — это то, будем ли мы проверять длину меньше 2 или меньше 1 .

³ first часто вызывается head по причинам, которые не стоит здесь обсуждать.

⁴ Ну, опять же, конечные

⁵ Вероятно, стоит извлечь reverseString из этого вспомогательную функцию по той же причине, по которой мы это делали first и last выше. Это действительно простая функция многократного использования. Это оставлено в качестве упражнения.

1. звездный пост. политики овладели искусством пустого говорения правды!

2. Мистер Скотт Сойет, большое вам спасибо! Ваш ответ мне очень помог! Теперь я определенно все понимаю в этой проблеме.

3. @MilosPopovic: Я рад, что это помогло. Пожалуйста, зовите меня Скотт.

Ответ №2:

Вы делаете .slice(1, -1) на неправильном элементе, потому что он сохраняет пробелы, и они не совпадают в палиндроме. И ваш код просто проверяет последние буквы в центре и забывает все остальные вокруг.

Я бы предпочел видеть код таким образом

 console.log(palindrome("Anne I vote more cars race Rome to Vienna"))

function palindrome( str )
  {
  return recussiv( str.replace(/[^A-Za-z0-9]/g, '').toLowerCase() )

  function recussiv(s)
    {
    console.log('-->', s )
    if (s.length > 1)
      {
      return (s[0] === s[s.length-1]) ? recussiv(s.slice(1, -1)) : false
      }
    else return true
    }
  }

 .as-console-wrapper { max-height: 100% !important; top: 0