Una stringa può avere un palindromo, esiste un modo migliore per farlo?

Question

ho avuto una domanda molto interessante intervista di oggi:

data una stringa, è necessario stabilire se la stringa potrebbe avere un palindromo quando permutato.

Quanto segue è l'implementazione che mi è venuta in mente. Ma c'è una soluzione migliore?

function canBePalindrome(someStr) { 
 

 
    if (typeof someStr !== "string") { 
 
     throw new Error("Expecting argument to be a string !"); 
 
    } 
 

 
    if (someStr.length == 1) return someStr; 
 
    var canBePalin = false; 
 
    var _chunks = someStr.split(""); 
 
    var _length = _chunks.length; 
 
    for (var i = 0; i < _length; i++) { 
 
     for (var j = i + 1; j < _length; j++) { 
 
     var temp_char = _chunks[i]; 
 
     _chunks[i] = _chunks[j]; 
 
     _chunks[j] = temp_char; 
 

 
     if (isPalindrome(_chunks.join(""))) return true; 
 

 
     } 
 
    } 
 
    return canBePalin; 
 

 
    } //End of canBePalindrome 
 

 

 
function isPalindrome(someStr) { 
 
    //console.log("Checking for:"+someStr); 
 
    var original = someStr.split(""); 
 
    return someStr === original.reverse().join(""); 
 
    } //End of isPalindrome 
 

 
canBePalindrome("mdadm");

questo non sarebbe un possibile duplicato perché, non sto controllando se è palindromo direttamente, ma permutando e controllarlo.

Answer 1

Se tutte le lettere in una stringa hanno un conteggio pari, eccetto che al più uno, è sempre possibile riorganizzarle in un palindromo. La mia soluzione è un po 'più lunga di altre perché ho cercato di ridurre al minimo il sovraccarico delle prestazioni dei loop con funzioni e creazione di array non necessaria.

aaaabbbb => aabbbbaa 
aaaabbbbc => aabbcbbaa 


function isPalindromable(str) { 
    var map = getCharCount(str); 
    var nonPairs = 0; 
    for (var char in charMap) { 
     if (charMap[char] % 2 != 0) 
      nonPairs++; 
     if (nonPairs > 1) 
      return false; 
    } 
    return true; 
} 

function getCharCount(str) { 
    // Number of times each string appeared 
    var map = {}; 
    for (var i = 0; i < str.length; i++) { 
     var ch = str.charAt(i); 
     map[ch] = ++map[ch] || 1; 
    } 
    return map; 
} 

Se vi piace un liner (non così rapidamente, ma tipo di eleganti)

function isPalindromable(str) { 
    var charMap = getCharCountMap(str); 
    return Object.keys(charMap).filter(char => charMap[char] %2 > 0).length <= 1; 
} 

function getCharCountMap(str) { 
    return str.split('').reduce((prev, cur) => (prev[cur] = ++prev[cur] || 1, prev) , {}) 
} 

Performance Edit

I benchmark le tre soluzioni. Il mio era il più lento quando le corde erano corte e più veloce per le corde più lunghe. Tuttavia, un amico al lavoro ha trovato una soluzione che risulta essere la più veloce, forse perché ha solo un ciclo ma non ha bisogno di ordinare. http://jsperf.com/can-string-be-made-into-palindrome/2

function canBePalindromeReplace(string) { 
    var oddCount = 0; 

    while(string.length > 0) { 
     var char = string.charAt(0); 
     var stringLength = string.length; 
     string = string.replace(new RegExp(char, 'g'), ''); 
     var diff = stringLength - string.length; 
     if((diff % 2) != 0) { 
      oddCount++; 
      if(oddCount > 1) { 
       return false; 
      } 
     } 
    } 

    return true; 
} 

Answer 2

Un bel trucco è quello di vedere le seguenti proprietà di un palindromo:

• Quando la dimensione della stringa è coppia, allora tutti i caratteri dovrebbe comparire una serie paio di volte.
• Se la dimensione della stringa è dispari, tutti i caratteri ma uno devono apparire un paio di volte.

Con queste informazioni è possibile scrivere un algoritmo per il conteggio dei tempi in cui ogni possibile carattere viene visualizzato nella stringa, quindi verificare se è conforme alle proprietà precedenti. Questo algoritmo dovrebbe avere la complessità temporale O(N + M), dove N è la dimensione della stringa e M è la quantità di possibili caratteri che possono apparire nella stringa. Ad esempio, se la stringa ha solo caratteri ASCII, allora ha la complessità temporale O(N + 255). La complessità dello spazio è di O(N + M).

Answer 3

Penso che un modo migliore sia quello di creare un array di lunghezza 26, arr[26]. Uno per ogni lettera. Quindi passa attraverso la corda aumentando la frequenza di ogni lettera man mano che si verificano.

Una volta terminato, passare attraverso lo arr[] e controllare se tutte le frequenze sono pari o meno. C'è spazio solo per un personaggio con una frequenza strana, quello che possiamo mettere nel mezzo del palindromo.

Se tutte le frequenze sono pari, allora può essere organizzata come un palindromo.

Altrimenti no.

---

L'algoritmo dovrebbe essere simile a questo

str[] holding the string; 
create arr[26] and intialize with 0; 

for char in str: 
    arr[char]++ //char should be mapped to its index properly 
       // like a = 0, b = 1 and so on 

no_of_odd_char = 0 
for freq in arr: 
    if(freq % 2 == 1) 
     if(no_of_odd_char == 1) 
      print "cannot be palindrome" 
      exit() 
     else if(no_of_odd_char == 0) 
      no_of_odd_char = 1 

print "can be palindrome" 

Answer 4

Mantenere una mappa di caratteri, contarli, e vedere se il conteggio è anche per tutti i caratteri, se lo è, un palindromo può essere creato

function canBePalindrome(someStr) { 
    var map = {}; 
    var arr = someStr.split(''); 

    arr.forEach(function(s) { 
     s in map ? map[s]++ : map[s] = 1; 
    }); 

    var len = Object.keys(map).filter(function(o) { 
     return map[o] % 2; 
    }).length; 

    return arr.length % 2 ? len === 1 : len === 0; 
} 

FIDDLE

A "giocato a golf" la versione di quanto sopra sarebbe b e

function canBePalindrome(someStr) { 
    return (function(m, a, l) { 
     a.forEach(function(s) { s in m ? m[s]++ : m[s] = 1 }); 
     l = Object.keys(m).filter(function(o) { return m[o] % 2 }).length; 
     return a.length % 2 ? l === 1 : l === 0; 
    })({}, someStr.split('')); 
} 

Answer 5

Esiste una permutazione della stringa che è palindroma se e solo se il numero di caratteri che appaiono un numero dispari di volte è 0 o 1.

function canBePalindrome(str) { 
    var isOdd = Object.create(null), 
     numOdd = 0; 
    for(let ch of str) 
    numOdd += (isOdd[ch] = !isOdd[ch]) * 2 - 1; 
    return numOdd <= 1; 
} 

È possibile scorrere con for(var i=0; i<str.length; ++i) per sostenere pre -ES6 implementazioni, ma che non funzioneranno correttamente se la stringa contiene punti di codice unicode oltre i primi 16 bit dell'intervallo del punto di codice.

Answer 6

soluzione utilizzando ordinare e impilare:

function canBePalindrome(someStr) { 
    var stack = []; 
    someStr.split('').sort().forEach(function(ch) { 
     stack[stack.length - 1] === ch ? stack.pop() : stack.push(ch); 
    }); 
    return stack.length < 2; 
}