检查字符串中的重复字符 Javascript

Question

我想知道是否有一种方法可以在不使用双循环的情况下检查字符串中的重复字符。这可以用递归来完成吗？

使用双循环的代码示例（return 判断是否正确取决于字符串中是否存在重复字符）：

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

您可以使用 .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 2

（这个答案的最后可以找到递归的解决方案。）

您可以只使用内置的 javascript 数组函数 some MDN some reference

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

callback parameters:
v ... current value of the iteration
i ... current index of the iteration
a ... array being iterated

.split("") create an array from a string
.some(function(v,i,a){ ... }) goes through an array until the function returns true, and ends than right away. (it doesn't loop through the whole array, which is good for performance)

Details to the some function here in the documentation

测试，有几个不同的字符串：

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 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²)。

所以最好使用对象来映射和记住字符来检查唯一性或重复性。假设每个字符的最大数据大小，这个过程将是一个 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 /(.).*/.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 !/(.).*/.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'
    }
}

Answer 6

另一种使用 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()));

Answer 7

您可以使用 "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.

Read more about Sets at MDN

这里是我的使用方法：

 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

Answer 8

使用正则表达式求解=>

function isIsogram(str){
  return !/(\w).*/i.test(str);
}

console.log(isIsogram("isogram"), true );
console.log(isIsogram("aba"), false, "same chars may not be adjacent" );
console.log(isIsogram("moOse"), false, "same chars may not be same case" );
console.log(isIsogram("isIsogram"), false );
console.log(isIsogram(""), true, "an empty string is a valid isogram" );

Answer 9

 const str = "afewreociwddwjej";
  const repeatedChar=(str)=>{
  const result = [];
  const strArr = str.toLowerCase().split("").sort().join("").match(/(.)+/g);
  
  if (strArr != null) {
    strArr.forEach((elem) => {
      result.push(elem[0]);
    });
  }
  return result;
}
console.log(...repeatedChar(str));

您还可以使用以下代码查找字符串中重复的字符

Answer 10

//Finds character which are repeating in a string
var sample = "success";
function repeatFinder(str) {
    let repeat="";
    for (let i = 0; i < str.length; i++) {
        for (let j = i + 1; j < str.length; j++) {
            if (str.charAt(i) == str.charAt(j) && repeat.indexOf(str.charAt(j)) == -1) {
                repeat += str.charAt(i);
            }
        }
    }
    return repeat;
}
console.log(repeatFinder(sample)); //output: sc

Answer 11

let myString = "Haammmzzzaaa";

myString = myString
   .split("")
   .filter((item, index, array) => array.indexOf(item) === index)
   .join("");
   
console.log(myString); // "Hamza"

检查字符串中的重复字符 Javascript

Check for repeated characters in a string Javascript

javascript

recursion

repeat