palabra - split javascript array

Compruebe si hay caracteres repetidos en una cadena Javascript

Question

Me preguntaba si hay una forma de verificar si hay caracteres repetidos en una cadena sin usar doble bucle. ¿Se puede hacer esto con la recursión?

Un ejemplo del código que usa doble bucle (devuelve verdadero o falso en función de si hay caracteres repetidos en una cadena):

var charRepeats = function(str) {
    for(var i = 0; i <= str.length; i++) {
        for(var j = i+1; j <= str.length; j++) {
            if(str[j] == str[i]) {
                return false;
            }
        }
    }
    return true;
}

¡Muchas gracias de antemano!

Answer 1

puede usar .indexOf() y .lastIndexOf() para determinar si se repite un índice. Es decir, si la primera aparición del personaje es también la última ocurrencia, entonces sabes que no se repite. Si no es cierto, entonces se repite.

var example = ''hello'';

var charRepeats = function(str) {
    for (var i=0; i<str.length; i++) {
      if ( str.indexOf(str[i]) !== str.lastIndexOf(str[i]) ) {
        return false; // repeats
      }
    }
  return true;
}

console.log( charRepeats(example) ); // ''false'', because when it hits ''l'', the indexOf and lastIndexOf are not the same.

Answer 2

El algoritmo presentado tiene una complejidad de (1 + n - (1)) + (1 + n - (2)) + (1 + n - (3)) + ... + (1 + n - (n-1)) = (n-1)*(1 + n) - (n)(n-1)/2 = (n^2 + n - 2)/2 que es O (n ² ).

Por lo tanto, sería mejor usar un objeto para mapear y recordar a los personajes para verificar si son únicos o duplicados. Suponiendo un tamaño de datos máximo para cada personaje, este proceso será un algoritmo O(n) .

function charUnique(s) {
  var r = {}, i, x;
  for (i=0; i<s.length; i++) {
    x = s[i];
    if (r[x])
      return false;
    r[x] = true;
  }
  return true;
}

En un pequeño caso de prueba, la función de hecho funciona unas pocas veces más rápido.

Tenga en cuenta que las cadenas de JavaScript se definen como secuencias de valores enteros sin signo de 16 bits. http://bclary.com/2004/11/07/#a-4.3.16

Por lo tanto, aún podemos implementar el mismo algoritmo básico pero utilizando una búsqueda de matriz mucho más rápida en lugar de una búsqueda de objetos. El resultado es aproximadamente 100 veces más rápido ahora.

var charRepeats = function(str) {
  for (var i = 0; i <= str.length; i++) {
    for (var j = i + 1; j <= str.length; j++) {
      if (str[j] == str[i]) {
        return false;
      }
    }
  }
  return true;
}

function charUnique(s) {
  var r = {},
    i, x;
  for (i = 0; i < s.length; i++) {
    x = s[i];
    if (r[x])
      return false;
    r[x] = true;
  }
  return true;
}

function charUnique2(s) {
  var r = {},
    i, x;
  for (i = s.length - 1; i > -1; i--) {
    x = s[i];
    if (r[x])
      return false;
    r[x] = true;
  }
  return true;
}

function charCodeUnique(s) {
  var r = [],
    i, x;
  for (i = s.length - 1; i > -1; i--) {
    x = s.charCodeAt(i);
    if (r[x])
      return false;
    r[x] = true;
  }
  return true;
}

function regExpWay(s) {
  return /(.).*/1/.test(s);
}


function timer(f) {
  var i;
  var t0;

  var string = [];
  for (i = 32; i < 127; i++)
    string[string.length] = String.fromCharCode(i);
  string = string.join('''');
  t0 = new Date();
  for (i = 0; i < 10000; i++)
    f(string);
  return (new Date()) - t0;
}

document.write(''O(n^2) = '',
  timer(charRepeats), '';<br>O(n) = '',
  timer(charUnique), '';<br>optimized O(n) = '',
  timer(charUnique2), '';<br>more optimized O(n) = '',
  timer(charCodeUnique), '';<br>regular expression way = '',
  timer(regExpWay));

Answer 3

(Una solución recursiva se puede encontrar al final de esta respuesta).

Podría usar javascript incorporado Array funciones algunas MDN alguna referencia

 var text = "test".split("");
 text.some(function(v,i,a){
   return a.lastIndexOf(v)!=i;
 });

parámetros de devolución de llamada:
v valor actual de la iteración
i índice actual de la iteración
una matriz actual

.split ("") crea una matriz a partir de una cadena
.some (function (v, i, a) {...}) pasa por una matriz hasta que la función returns true , y termina de inmediato. (no recorre toda la matriz, si encuentra una coincidencia anterior)

Los detalles de algunas funciones se pueden encontrar aquí

Pruebas, con varias cadenas:

var texts = ["test", "rest", "why", "puss"];


for(var idx in texts){
    var text = texts[idx].split("");
    document.write(text + " -> " + text.some(function(v,i,a){return a.lastIndexOf(v)!=i;}) +"<br/>");
    
  }
  //tested on win7 in chrome 46+

Si la recursión es necesaria.

Actualización para la recursión:

//recursive function
function checkString(text,index){
    if((text.length - index)==0 ){ //stop condition
        return false; 
    }else{
        return checkString(text,index + 1) 
        || text.substr(0, index).indexOf(text[index])!=-1;
    }
}

// example Data to test
var texts = ["test", "rest", "why", "puss"];

for(var idx in texts){
    var txt = texts[idx];
    document.write( txt +  " ->" + checkString(txt,0) + "<br/>");
}
//tested on win7 in chrome 46+

Answer 4

Esto lo hara:

function isIsogram (str) {
    return !/(.).*/1/.test(str);
}

Answer 5

function chkRepeat(word) {
    var wordLower = word.toLowerCase();
    var wordSet = new Set(wordLower);
    var lenWord = wordLower.length;
    var lenWordSet =wordSet.size;

    if (lenWord === lenWordSet) {
        return "false"
    } else {
        return''true''
    }
}