檢查一個字符串是否可以由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