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

Question

我有两个字符串，string1和string2。我想检查string1是否可以由string2中的字符组成（没有重复字符）。例如，如果string1是“工具”，string2是“环礁”，函数将返回false。如果string1是“触摸”，string2是“chetoudce”，它将返回true。

在Javascript中最有效的方法是什么？我在考虑使用indexOf，然后从string2中删除用来构建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

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

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

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

首先，统计每个字符串中的字符。然后，如果超字符串的每个字符的数量大于或等于子字符串，则返回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