我想知道是否有一种方法可以在不使用双循环的情况下检查字符串中的重复字符。这可以用递归来完成吗？
使用双循环的代码示例（根据字符串中是否有重复字符返回真或假）：
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;
}
提前谢谢了！
（可以在此答案的末尾找到递归解决方案。）
您可以使用 javascript 内置数组函数some MDN 一些参考
var text = "test".split("");
text.some(function(v,i,a){
return a.lastIndexOf(v)!=i;
});
回调参数：
v 当前迭代值
i 当前迭代索引
a 当前数组.split("") 从一个字符串创建一个数组
.some(function(v,i,a){ ... }) 遍历一个数组直到函数returns true，然后立即结束。（不循环遍历整个数组，如果它更早找到匹配项）可以在此处找到某些功能的详细信息
测试，有几个字符串：
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+这将：
function isIsogram (str) {
return !/(.).*\1/.test(str);
}
您可以使用.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.
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'
}
}
所提出的算法的复杂度(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));