1

我有两个字符串，string1 和 string2。我想检查string1是否可以由string2中的字符组成（不重复字符）。例如，如果string1是“tool”，string2是“atoll”，函数将返回false。如果string1是“touch”并且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;
}
4

4 回答 4

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
于 2012-07-12T23:04:10.333 回答
1

这可以在 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;
于 2012-07-12T23:09:07.817 回答
1

这是我的第一个想法。

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

如果输入已排序，则合并连接速度很快。显然，在浏览器中对两个数组进行排序比对每个字符串执行多个正则表达式操作要快。

编辑：我刚刚意识到我的想法 #2 基本上是 Kolink 算法的副本。但是，我的功能具有一致的性能优势。在分析它们的差异时可能会发现一些有趣的结果。

另外，我发现在#2 中，我不应该counts[char] -= 1;向上移动一条线，但我不想破坏我已经在 jsperf 获得的性能结果。所以我要离开它，因为它不会不公平地扭曲结果，因为它只会损害函数的性能。

在 jsperf 自己做速度测试！

于 2012-07-12T23:25:12.883 回答
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

于 2012-07-12T23:36:48.787 回答