我写了一个解决方案，最坏情况下的时间复杂度为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++) {
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;
};
您可以通过仅在首次调用
findCombination()时初始化
mappedDict变量，而不是每次调用时都初始化，来优化代码。
['aaabc'、'aabbc'、'abbcc'、'aabcc' 等）），你不可能做得比 O(2^n) 更好。但我认为你可以优化常见场景，例如你可以创建一个表示单词部分顺序的图表，基于我的subtract（）方法，其中如果您可以从 a 中减去 b，则a < b` 。一旦您拥有了这张图表，您就可以在减法失败时排除整个分支。 - Elian Ebbing