编写函数，通过1个字符的JavaScript匹配单词

Writing function to Match words off by 1 character JavaScript

本文关键字：JavaScript 单词 字符 1个 函数 通过      更新时间：2024-02-25

我正在尝试编写一个JavaScript函数OneLetterOff，它将接收一个String和一个接受单词数组（WordList）。

它应该返回一个来自WordList的单词数组，这些单词与String中给定的单词在单个位置仅相差一个字母。

例如：

WordList = ["marc", "bark", "parc", "shark", "mark"];
OneLetterOff("park", WordList); // should return ["bark", "parc", "mark"]

通过测试的单词必须具有相同的长度，我们可以放心地假设它们都是小写字母。

如何使用正则表达式来求解此算法？本质上，除了必须使用正则表达式来解决它之外，还有其他方法吗？

非常感谢你的帮助。

正则表达式不是最好的，但可以给你一个想法：

"mark".match(/.ark|p.rk|pa.k|par./) //true

当然，您可以自动构建正则表达式，而"."可能不是您想要的，这取决于您需要包含的可能字符。

我建议你自己解决剩下的问题，因为它看起来很像家庭作业；-）

有很多非正则表达式的方法可以解决这个问题。对于简短的单词来说，预编译的正则表达式可能是最有效的。

您正在列表中查找与给定单词的Levenstein距离为1的单词。

正如在Algorithm Implementation/Strings/Levenstein距离中发现的那样，该算法的JavaScript实现如下：

function levenshteinDistance (s, t) {
        if (s.length === 0) return t.length;
        if (t.length === 0) return s.length;
        return Math.min(
                levenshteinDistance(s.substr(1), t) + 1,
                levenshteinDistance(t.substr(1), s) + 1,
                levenshteinDistance(s.substr(1), t.substr(1)) + (s[0] !== t[0] ? 1 : 0)
        );
};

使用Array.prototype.filter（IE<9所需的polyfill）只包括距离为1的项目的方法，我们得到了一个非常简单的代码：

var oneLetterOff = function (word, list) {
   return list.filter(function (element) {
       return levenshteinDistance(word, element) === 1;
   });
};
oneLetterOff('park', ['marc', 'bark', 'parc', 'shark', 'mark']);
// returns ["bark", "parc", "mark"]

这种方法的一个很好的特点是，它适用于任何距离——只需改变你在过滤器中比较的内容。

如果你真的想使用正则表达式（我不建议使用），你需要：

  1. 迭代给定的单词以创建一组表示正则表达式子模式的字符串，其中每个子模式都有一个可选字符
  2. 使用new RegExp()将这些字符串子模式组合成一个正则表达式
  3. 将测试单词的列表与表达方式进行对比
  4. 当你得到一个匹配项时，将其添加到一组匹配项中
  5. 返回匹配集

写这篇文章不会花很长时间，但考虑到我上面给出的答案，我想你会同意这是一种愚蠢的方法。

这是我的解决方案，灵感来自JAAuide，并使用了JavaScript函数的所有功能

function lDist (s, t) { 
  /* If called with a numeric `this` value 
       returns true if Levenshtein distance between strings s and t <= this
     else
       returns the Levenshtein distance between strings s and t                         */
  return this.constructor === Number ? lDist.call (null, s, t) <= this :
     s.length && t.length 
       ? Math.min (lDist (s.slice (1), t) + 1,
                   lDist (t.slice (1), s) + 1,
                   lDist (s.slice (1), t.slice (1)) + (s.charAt (0) !== t.charAt (0)))
       : (s.length || t.length) };
['marc', 'bark', 'parc', 'shark', 'mark'].filter (lDist.bind (1, 'park'));

请参阅jsFiddle

相关文章：