如何比较字符串并检查阈值相等性？

Question

我需要比较字符串，并且想要测试它们的字符最多不同 a 个元素，例如：

// for a = 2 comparing all strings with str1
var str1 = 'qwerty'; // should return true
var str2 = 'qwerty'; // should return true
var str3 = 'qw1rty'; // should return true
var str4 = '1wery1'; // should return true
var str5 = 'q1e11y'; // should return false

为了完成这个任务，我创建了一个函数，虽然它能够工作，但我想知道是否可以使用正则表达式来实现。我的实际函数如下：

function test(str1, str2, limit) {
  const occ = str1.split('').reduce((acc, char, idx) => str2[idx] == char ? ++acc : acc, 0);
  return str1.length - occ <= limit;
}

// for a = 2 comparing all strings with str1
var str1 = 'qwerty'; // should return true
var str2 = 'qwerty'; // should return true
var str3 = 'qwert1'; // should return true
var str4 = 'qwer11'; // should return true
var str5 = 'qwe111'; // should return false

console.log(test(str1, str1, 2)) // true
console.log(test(str1, str2, 2)) // true
console.log(test(str1, str3, 2)) // true
console.log(test(str1, str4, 2)) // true
console.log(test(str1, str5, 2)) // false

有没有一种使用正则表达式实现这个的方法？

- guijob

---

它（容易地）可以通过比“JS”更好的正则表达式引擎来实现 - 它一定要是“JavaScript”吗？ - Jan

我实际上正在使用 node 进行服务器端处理，所以 javascript 是必需的。 - guijob

附注：Levenshtein Distance是一种类似但更高级的算法。 - str

https://codepen.io/anon/pen/wyVzvp?editors=0110 - Hackerman

@guijob: 真可惜，看看 https://paste.ofcode.org/pmvuNLhkPtgXW9PdQiDnRS 中不到10行的Python示例。 - Jan

Answer 1

您可以使用正则表达式来匹配当前正确的字母。如果没有匹配，就捕获当前字符。然后计算捕获字符的数量并进行比较。对于单词qwerty，这将是正则表达式：

(?:q|(.))(?:w|(.))(?:e|(.))(?:r|(.))(?:t|(.))(?:y|(.))

JS代码：

function testDistance(str1, str2, limit) {
    reStr = '(?:' + str1.split('').join('|(.))(?:') + '|(.))';
    return (new RegExp(reStr)).exec(str2).filter(Boolean).length - 1 <= limit;
}

var str1 = 'qwerty'; // should return true
var str2 = 'qwerty'; // should return true
var str3 = 'qwert1'; // should return true
var str4 = 'qwer11'; // should return true
var str5 = 'qwe111'; // should return false

console.log(testDistance(str1, str1, 2)) // true
console.log(testDistance(str1, str2, 2)) // true
console.log(testDistance(str1, str3, 2)) // true
console.log(testDistance(str1, str4, 2)) // true
console.log(testDistance(str1, str5, 2)) // false

- revo

---

它对我的输入不起作用，请看一下这里。 - guijob

为什么这个 1wery1 应该返回 true？这个字符串有 3 个字符在不同的位置与原始字符串不匹配。 - revo

太棒了，你做到了！ - guijob

Answer 2

你可以使用以下代码从给定的字符串创建正则表达式。然后计算正则表达式与其他字符串的匹配次数，以确定距离：

function test(str1, str2, limit) {
  // First: Create a regexp from the given input string:
  // "qwerty" -> ["q","w","e","r","t","y"]
  //          -> ["(q)?","(w)?","(e)?","(r)?","(t)?","(y)?"] 
  //          -> (q)?(w)?(e)?(r)?(t)?(y)?
  let regexp = new RegExp(str1.split('').map(e => `(${e})?`).join(''));

  let match = str2.match(regexp);
  if(!match) {
    return false;
  }
  // Now calculate the matches, which did not fulfill the question mark regexp brackets.
  let notEmpty = function(e) { return e; };

  return str2.length - (match.filter(notEmpty).length - 1) <= limit;
}

- Timm

---

它对我的输入不起作用。请看这里：（https://codepen.io/anon/pen/BYXLXv?editors=1010）。 - guijob