检查一个字符串是否可以由Javascript中另一个字符串中的字符组成

Question

我有两个字符串string1和string2。我想检查string1是否可以由string2中的字符组成（不重复字符），例如，如果string1是“tool”而string2是“atoll”，则函数将返回false;如果string1是“touch”并且string2是“chetoudce”，它将返回true。

什么是最有效的方式来做到这一点在Javascript中？我想使用indexOf，然后删除从字符串2中使用的字符来构建string1，但我认为创建这个辅助字符串可能有性能问题

编辑：我做了这个基于第一反应，那就是：

function isSubsetOf(a, b){ 
    if(a.length > b.length){ 
     return false; 
    } 

    while(a.length > 0){ 
     var letter = a.substr(0, 1), 
      re = new RegExp(a.substr(0, 1), 'g'), 
      a_count = (a.match(re)||[]).length, 
      b_count = (b.match(re)||[]).length; 

     if(a_count > b_count){ 
      return false; 
     } 

     a = a.replace(re, ''); 
    } 
    return true; 
} 

Answer 1

首先，计算每个字符串中的字符。然后，如果超字符串的每个字符的子数大于或等于子字符串，则返回true。

O（m + n），对于m和n是子字符串和超字符串的大小。

例子：

Superstring: aaaaabbbbccc 
Substring: aabbcc 

Superstring letters: 
    a: 5 
    b: 4 
    c: 3 
    all others: 0 
Substring letters: 
    a: 2 
    b: 2 
    c: 2 
    all others: 0 

5 >= 2, 4 >= 2, 3 >= 2, so true 

Answer 2

这可以在O（n）的时间来完成：

string1 = "touch"; 
string2 = "chetoudce"; 

var chars = {}, l = string2.length, i; 
for(i=0; i<l; i++) chars[string2[i]] = (chars[string2[i]] || 0)+1; 

l = string1.length; 
for(i=0; i<l; i++) { 
    if(chars[string1[i]]) chars[string1[i]]--; 
    else return false; 
} 
return true; 

Answer 3

这是我的第一个想法。

function isSubsetOf(elements, set) { 
    var i, l = elements.length, pos; 
    set = set.split(''); 
    for (i = 0; i < l; i += 1) { 
     pos = set.indexOf(elements.charAt(i)); 
     if (pos == -1) return false; 
     set.splice(pos, 1); 
    } 
    return true; 
} 

/*-- Algorithm: --*/ 
// for each character in *elements*: 
// remove that character from an array of *set*'s characters 
// (and if not found, return false). 

但是，我不知道，IE没有Array.indexOf，这使得这个可怕的失败者中的IE浏览器性能方面有符合标准的indexOf功能添加到Array.prototype。但令我惊讶的是，它只是与Chrome的尖叫，这显然是一个平均拼接运算机器。

我的第二个想法比我的第一个想法更好，但并不比页面上的其他人好得多。

function isSubsetOf2(elements, set) { 
    var i, l, counts = {}; 
    for (i = 0, l = set.length; i < l; i += 1) { 
     char = set.charAt(i); 
     counts[char] = (counts[char] || 0) + 1; 
    } 
    for (i = 0, l = elements.length; i < l; i += 1) { 
     char = elements.charAt(i); 
     if (!counts[char]) return false; 
     counts[char] -= 1; 
    } 
    return true; 
} 

/*-- Algorithm: --*/ 
// For each character in *set*: 
// increment its count in an object "map". 
// For each character in *elements* 
// decrement its count in an object map 
// (and if < 0 or doesn't exist, return false) 

所以，最后，我的第三个想法是最快的Firefox和良好的全方位的竞争者，但不同的浏览器显示不同功能的速度有很大的不同的配置文件。

function isSubsetOf3(elements, sets) { 
    var e, s, el = elements.length, sl = sets.length; 
    elements = elements.split('').sort(); 
    sets = sets.split('').sort(); 
    for (e = 0, s = 0; e < el; e += 1, s += 1) { 
     while (s < sl && sets[s] < elements[e]) { s += 1; } 
     if (s == sl || sets[s] > elements[e]) { return false }; 
    } 
    return true; 
} 

/*-- Algorithm: --*/ 
// Sort arrays of the characters in *elements* and *set*. 
// Do a logical "merge join" (cool!) and: 
// if no match is found, return false 
// MERGE JOIN: 
// For each character in the *elements* array ("left" input) 
// Consume one matching character from *set* ("right" input) 
//  (skipping matches that are less than the character) 
// And if *set* runs out of characters or is higher than *element*, return false 

如果对输入进行排序，则合并联接为FAST。显然，在浏览器中对两个数组进行排序比对每个字符串执行多个Regex操作要快。

编辑：我刚刚意识到我的想法＃2基本上是Kolink算法的重复。但是，我的功能有一致的性能优势。分析其差异可能会发现一些有趣的结果。

另外，我发现在＃2中，我不应该将counts[char] -= 1;调高一行，但我不想吹掉我已经在jsperf上获得的性能结果。所以我要离开它，因为它不会不公平地扭曲结果，因为它只会伤害函数的性能。

Do the speed tests yourself at jsperf！

Answer 4

这是一个简单的正则表达式解决方案。它与你的非常相似，除了它不做任何字符串操作，所以它可能会快一点。

function check(needle, haystack) { 

    var visited = {}, chr, i, re; 

    for (i = needle.length; i--;) { 
    chr = needle[i]; 
    if (visited[chr]) 
     continue; 
    re = new RegExp(chr, 'g'); 
    if ((haystack.match(re) || []).length < (needle.match(re) || []).length) 
     return false; 
    visited[chr] = true; 
    } 

    return true; 

} 

http://jsbin.com/uretim/edit#preview