Javascript:检查是否可以通过组合数组中的其他字符串来重新创建字符串？

Question

我试图找出检查是否可以通过组合我在数组中的其他字符串创建特定字符串的最佳方法.其他字符串可以是任意长度,包括一个字符.此外,可以重新排序其他字符串中的字符.

因此,如果我们正在寻找"闪避"这个词并且我们的字符串数组是['god','house','d','e','cat','c','r','jump'],我们就会有一个匹配,因为我们可以将'god','d'和'e'中的字母组合起来创建'闪避'.

如果数组包含"dot"而不是"d",我们就不会有匹配,因为我们必须使用我们重新组合的每个单词中的所有字符(我们必须使用'o'和't'作为好).

我还想知道哪些单词用于创建指定的单词,所以如果匹配,我希望函数返回重新组合的单词的数组索引以创建指定的单词.对于上面的"闪避"示例,它将返回[0,2,3].

Answer 1

我写了一个解决方案，它有最坏的情况O(2^n)，但在大多数情况下它都会表现得很好。我从一个函数开始，该函数将每个字符串映射到一个对象，该对象对字符串中的所有不同字母进行计数。例子：

map("dodge") --> { "d": 2, "e": 1, "g": 1, "o": 1, size: 5 }

正如您所看到的，它还将大小存储在结果中。这是实现：

function map(str) {
    var obj = { size: str.length };

    for(var i=0; i<str.length; i++) {   
        var ch = str.charAt(i);
        obj[ch] = (ch in obj) ? obj[ch]+1 : 1;
    }

    return obj;
}

然后我编写一个函数来“减去”两个映射对象。例如：

subtract(map("ab"), map("a")) --> { "b": 1, size: 1 }
subtract(map("dodge"), map("god")) --> { "d": 1, "e": 1, size: 1 }
subtract(map("abc"), map("abc")) --> { size: 0 }
subtract(map("a"), map("b")) --> null

正如您在上一个示例中所看到的，null如果无法进行减法，则该函数将返回。这是一个实现subtract：

function subtract(a, b) {
    var result = { size: 0 };

    for(var i=97; i<123; i++) { // from a to z (ASCII)
        var ch = String.fromCharCode(i);
        var diff = (a[ch] || 0) - (b[ch] || 0);

        if(diff < 0)
            return null;

        if(diff > 0) {
            result[ch] = diff;
            result.size += diff;
        }
    }
    return result;
}

最后一步是编写一个方法findCombination(word, dict)，如果找到任何组合，则返回一个组合，否则返回 null。例子：

var dict = ['god','house','d','e','cat','c','r','jump'];
findCombination("dodge", dict) --> [0, 2, 3]
findCombination("housecat", dict) --> [1, 4]
findCombination("hose", dict) --> null
findCombination("xyz", dict) --> null

我使用带有回溯的递归方法，尝试从给定键中“减去”单词，直到结果为“空”：

var findCombination = function(word, dict)
{
    var solution = [];
    var mappedDict = [];

    for(var i=0; i<dict.length; i++)
        mappedDict[i] = map(dict[i]);           

    var recursiveFind = function(key,  i)
    {
        if(i == mappedDict.length)
            return false;

        var result = subtract(key, mappedDict[i])

        if(result == null)
            return recursiveFind(key, i+1);

        solution.push(i);

        if(result.size == 0 || recursiveFind(result, i+1))
            return true;

        solution.pop();
        return recursiveFind(key, i+1);
    };

    if(recursiveFind(map(word), 0))
        return solution;

    return null;
};

mappedDict您可以（并且应该）通过仅初始化变量一次而不是每次findCombination()调用时来优化代码。