Ho un compito, che è quello di scramble una singola parola, la cui dimensione è maggiore di 3 lettere.
La parola criptata non deve essere uguale all'originale e la prima e l'ultima lettera della parola devono rimanere invariate.
Ad esempio, la parola stack , potrebbe dare uno dei seguenti risultati:
- satck
- scatk
- stcak
- sactk
- etc
Mentre parole come is o hey , ad esempio, rimarrebbero invariate per essere troppo piccole.
Il mio tentativo di farlo può essere visto sotto. Ho una funzione JavaScript che ha ricevuto una parola da scramble e quindi scelgo gli indici casuali entro un certo limite per creare una nuova parola criptata e restituirla. Se l'indice che ho scelto è già stato selezionato, quindi riprovo sperando in un nuovo risultato.
/**
* Returns a scrambled word with the first and last letters unchanged
* that is NOT EQUAL to the given parameter 'word', provided it has
* more than three characters.
*/
function scrambleWord(word){
if(word.length <= 3)
return word;
var selectedIndexes, randomCharIndex, scrambledWord = word;
while(word === scrambledWord){
selectedIndexes = [], randomCharIndex, scrambledWord = '';
scrambledWord += word[0];
for(var j = 0; j < word.length-2; j++){
//select random char index making sure it is not repeated
randomCharIndex = getRandomInt(1, word.length-2);
while(selectedIndexes.indexOf(randomCharIndex) > -1 && selectedIndexes.length != word.length-2){
randomCharIndex = getRandomInt(1, word.length-2);
}
scrambledWord += word[randomCharIndex];
selectedIndexes.push(randomCharIndex);
}
scrambledWord += word[word.length-1];
}
return scrambledWord;
}
/**
* Returns a random integer between min (inclusive) and max (inclusive)
* Using Math.round() will give you a non-uniform distribution!
* See: http://stackoverflow.com/a/1527820/1337392
*/
function getRandomInt(min, max) {
return Math.floor(Math.random() * (max - min + 1)) + min;
}
Il problema con questo approccio è che è troppo lento. Fallisco i test perché ho superato il limite di tempo di 6 secondi, quindi ho sicuramente bisogno di migliorare questa soluzione, ma non riesco a vedere dove posso farlo.
Da un punto di vista dell'algoritmo, qual è il modo più efficiente che utilizza il minor numero di operazioni nel caso peggiore in cui posso affrontare questo problema?