Проверка повторяющихся символов в строке Javascript

Question

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

Пример кода с использованием двойной петли (возвращение истина или ложь на основе, если повторяются символы в строке):

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; 
} 

Большое спасибо заранее!

Answer 1

(Рекурсивное решение может быть найдено в конце этого ответа.)

Вы можете использовать JavaScript встроенных функций массива некоторыеMDN some reference

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

Параметры обратного вызова:
v текущее значение итерации
I текущий индекс итерации
тока массива

.split ("") создать массив из строки
. Some (function (v, i, a) {...}) проходит через массив до функции returns true и заканчивается, чем сразу. (Не цикл через весь массив, если он находит соответствие ранее)

Детали к некоторые функции могут быть найдены here

тесты , с несколькими строками:

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+

Если требуется рекурсия.

Обновление для рекурсии:

//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 2

вы можете использовать .indexOf() и .lastIndexOf(), чтобы определить, повторяется ли индекс. Значение, если первое вхождение символа также является последним, вы знаете, что оно не повторяется. Если это не так, повторите.

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 3

Алгоритм, представленный имеет сложность (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, которая является О (п).

Таким образом, было бы лучше использовать объект для сопоставления и запоминания символов для проверки уникальности или дубликатов. Предполагая максимальный размер данных для каждого символа, этот процесс будет алгоритмом 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; 
} 

В крошечном тестовом случае функция действительно работает в несколько раз быстрее.

Обратите внимание, что строки JavaScript определяются как последовательности из 16-разрядных целых значений без знака. http://bclary.com/2004/11/07/#a-4.3.16

Следовательно, мы по-прежнему можем реализовать один и тот же базовый алгоритм, но используя гораздо более быстрый поиск массива, а не поиск объектов. Результат примерно в 100 раз быстрее.

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 4

Это будет делать:

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' 
    } 
}