javascript - 数组排列/组合

Question

我正在尝试找到检查字符串是否是的最佳方法

1. 等于单个索引处的数组值。
2. 等于数组的一个排列
3. 等于任何值的组合。
   3.1 这可以包括数组值与单词之间的空格的组合。
   3.2 这可以包括数组值的组合，单词之间没有空格。
4. 数组值本身不会有空格或特殊字符
5. 每个数组值都是唯一的。没有重复值。
6. 字符串中的单词永远不会超过两个。
7. 字符串中不会有特殊字符，但可以有空格。

有什么想法吗？

示例数据:

var stringExample = "application Name";

var arrayExample = ['app', 'application', 'name'];

伪:

for (var i = 0; i < arrayExample.length; i++) {
     if (stringExample.toLower() == arrayExample[i]) {
          return true;
     } elseif (stringExample.toLower() == "Any Combination of array values with spaces or
                       without spaces in between") { return true };
}

Answer 1

显然，输入字符串中的单词可能需要两个或更多数组元素的串联才能被视为匹配项。这可能是要求中最棘手的部分。

其次，似乎一旦一个单词与一个(或多个)数组值匹配，这些数组元素就不应再用于另一个匹配项。

我建议使用普通对象将数组值存储为属性。这将允许快速查找，并且删除(满足上面的第二点)也可以非常有效地完成。为了实现第一个要求，我会坚持使用蛮力方法。或者你可以构建一个 suffix tree ，但您需要大量投入才能从中受益，所以我不建议这样做。

在找到一个(部分)单词的潜在匹配项后，您可以使用递归来为较小的问题找到解决方案。

这是实现这些想法的 EcmaScript 3 解决方案:

function match(str, arr) {
    var words = str.toLowerCase().split(/\s+/);
    var keys = {};
    for (var i = 0; i < arr.length; i++) keys[arr[i].toLowerCase()] = 1;

    function recur(i) {
        if (i >= words.length) return true;
        var word = words[i];
        if (keys[word]) { // Try full match first - relatively fast operation
            keys[word] = 0;
            if (recur(i+1)) return true;
            keys[word] = 1; // backtrack: restore key
        } else { // Try partial match - relatively slow operation
            for (var key in keys) {
                if (!keys[key] || word.slice(0, key.length) !== key) continue;
                keys[word] = 0;
                words[i] = word.slice(key.length);
                if (recur(i)) return true;
                words[i] = word; // backtrack: restore word
                keys[word] = 1; // backtrack: restore key
            }
        }
        return false;
    }
    return recur(0);
}

var str = "application Name";
var arr = ['nam', 'me', 'applica', 'app', 'lication', 'na'];
console.log(match(str, arr));