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

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

Хэш-карта - это объект в Javascript, который имеет пару ключ-значение, которую можно использовать для текущего подсчета элементов.

Первое, что вам следует сделать, если вы столкнетесь с этой проблемой, - это спросить, какой палиндром обозначается буквами. Все мы знаем, что палиндром можно читать вперед и назад - популярными примерами являются «гоночный автомобиль» и «человек, планирующий канал Панама». С точки зрения количества символов, как определить палиндром?

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

aabb -> abba //True
aabbc -> abcba //True
aabbcc -> abccba //True
aaabbcc -> bcaaacb //True
aaabbb -> //False

Давайте посмотрим на каждый пример с точки зрения количества символов.

aabb
2(a)
2(b)
= All even counts = True
aabbc
2 (a)
2 (b)
1 (c)
= All even counts with only 1 odd count = True
aabbcc
2 (a)
2 (b)
2 (c)
= All even counts = True
aaabbb
3 (a)
3 (b)
= More than 1 set of odd counts = False

Теперь, когда мы определили палиндром с точки зрения того, что может определять компьютер, мы можем приступить к программированию. Сначала создается хэш-карта.

function isPalindrome(str){
    let hashmap = {}
    for(let i = 0; i < str.length; i++){
        if(str[i] === " ") continue
        let char = str[i].toLowerCase()
        if(hashmap[str[i]]){
            hashmap[str[i]]++
        } else {
            hashmap[str[i]] = 1
        }
    }
    console.log(hashmap)
}

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

console.log(isPalindrome("is this a palindrome"))
{ i: 3,
  s: 2,
  t: 1,
  h: 1,
  a: 2,
  p: 1,
  l: 1,
  n: 1,
  d: 1,
  r: 1,
  o: 1,
  m: 1,
  e: 1 }
console.log(isPalindrome("racecar"))
{ r: 2, 
  a: 2, 
  c: 2, 
  e: 1 }
console.log(isPalindrome("A man a plan a canal Panama")
{ a: 10, 
  m: 2, 
  n: 4, 
  p: 2, 
  l: 2, 
  c: 1 }

Я скопировал вывод для нескольких строк, чтобы увидеть, как выглядит каждый объект. Исходя из первоначального определения палиндрома, первая строка не подходит, потому что она не соответствует критериям. Вторая и третья строки соответствуют критериям и вернут истину.

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

Второй вариант - изменить наш первоначальный алгоритм. Ровный вид можно отменить. Если бы у нас была строка 'aa', итерация объекта была бы такой: 'a' - ›1, а затем 'a' -› 2. Вместо увеличения мы можем уменьшить: {'a': 1}, а затем {'a ': 0}.

function isPalindrome(str){
    let hashmap = {}
    for(let i = 0; i < str.length; i++){
        if(str[i] === " ") continue
        let char = str[i].toLowerCase()
        if(hashmap[str[i]]){
            hashmap[str[i]]-- //Updated from ++ to --
        } else {
            hashmap[str[i]] = 1
        }
    }
    let arr = []
    for(let char in hashmap)
        if(hashmap[char] > 0)
            arr.push(char)
    return arr.length === 1 || arr.length === 0
}