检查字符串 Javascript 中的重复字符
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/33656708/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Check for repeated characters in a string Javascript
提问by yinjia
I was wondering if there is a way to check for repeated characters in a string without using double loop. Can this be done with recursion?
我想知道是否有一种方法可以在不使用双循环的情况下检查字符串中的重复字符。这可以通过递归完成吗？
An example of the code using double loop (return true or false based on if there are repeated characters in a string):
使用双循环的代码示例（根据字符串中是否有重复字符返回真或假）：
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;
}
Many thanks in advance!
提前谢谢了！
采纳答案by winner_joiner
(A recursive solution can be found at the end, of this answer.)
（可以在此答案的末尾找到递归解决方案。）
You could use javascript builtin Array functions someMDN some reference
您可以使用 javascript 内置 Array 函数一些MDN 一些参考
var text = "test".split("");
text.some(function(v,i,a){
return a.lastIndexOf(v)!=i;
});
callback parameters:
vcurrent value of the iteration
icurrent index of the iteration
acurrent array.split("")create an array from a string
.some(function(v,i,a){ ... })goes through an array until the functionreturns true, and ends than right away. (doesn't loop through the whole array, if it finds an match earlier)Details to the somefunction can be found here
回调参数：
v当前迭代值
i当前迭代索引
a当前数组.split("")从一个字符串创建一个数组
.some(function(v,i,a){ ... })遍历一个数组直到函数returns true，然后立即结束。（不循环遍历整个数组，如果它更早找到匹配项）可以在此处找到某些功能的详细信息
Tests, with several strings:
测试，有几个字符串：
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+If recursion is needed.
如果需要递归。
Update for recursion:
递归更新：
//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+回答by thedarklord47
This will do:
这将：
function isIsogram (str) {
return !/(.).*/.test(str);
}
回答by j.Doe
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'
}
}
回答by Joseph Myers
The algorithm presented has a complexity of (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)/2which is O(n2).
所提出的算法的复杂度(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)。
So it would be better to use an object to map and remember the characters to check for uniqueness or duplicates. Assuming a maximum data size for each character, this process will be an O(n)algorithm.
因此最好使用对象来映射并记住字符以检查唯一性或重复项。假设每个字符的最大数据大小，这个过程将是一个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;
}
On a tiny test case, the function indeed runs a few times faster.
在一个很小的测试用例上，该函数的运行速度确实快了几倍。
Note that JavaScript strings are defined as sequences of 16-bit unsigned integer values. http://bclary.com/2004/11/07/#a-4.3.16
请注意，JavaScript 字符串被定义为 16 位无符号整数值的序列。http://bclary.com/2004/11/07/#a-4.3.16
Hence, we can still implement the same basic algorithm but using a much quicker array lookup rather than an object lookup. The result is approximately 100 times faster now.
因此，我们仍然可以实现相同的基本算法，但使用更快的数组查找而不是对象查找。结果现在快了大约 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 /(.).*/.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));回答by Prefix
you can use .indexOf()and .lastIndexOf()to determine if an index is repeated. Meaning, if the first occurrence of the character is also the last occurrence, then you know it doesn't repeat. If not true, then it does repeat.
您可以使用.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.
回答by pride
Another way of doing it using lodash
使用 lodash 的另一种方法
var _ = require("lodash");
var inputString = "HelLoo world!"
var checkRepeatition = function(inputString) {
let unique = _.uniq(inputString).join('');
if(inputString.length !== unique.length) {
return true; //duplicate characters present!
}
return false;
};
console.log(checkRepeatition(inputString.toLowerCase()));
回答by Klodian Koni
You can use "Set object"!
您可以使用“设置对象”！
The Set object lets you store unique values of any type, whether primitive values or object references. It has some methods to add or to check if a property exist in the object.
Set 对象允许您存储任何类型的唯一值，无论是原始值还是对象引用。它有一些方法可以添加或检查对象中是否存在属性。
Here how i use it:
这是我如何使用它：
function isIsogram(str){
let obj = new Set();
for(let i = 0; i < str.length; i++){
if(obj.has(str[i])){
return false
}else{
obj.add(str[i])
}
}
return true
}
isIsogram("Dermatoglyphics") // true
isIsogram("aba")// false
