檢查字符串中重複的字符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' 
    } 
}