检查字符串中重复的字符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; 
} 

非常感谢：

采用双循环的代码的例子（如果有一个字符串重复的字符返回true或false根据）！

Answer 1

（递归解决方案可以在年底发现，这个答案的。）

你可以使用JavaScript内置阵列功能一些MDN some reference

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

回调参数：
v的迭代
迭代
我当前索引一个当前数组

.split（ “”）的电流值创建来自字符串的数组
.some（函数（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 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' 
    } 
}