1

string1とstring2の2つの文字列があります。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

これは単純な正規表現ソリューションです。文字列操作を行わないことを除いて、あなたのものと非常に似ているため、少し高速になる可能性があります。

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 に答える
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 に がないことを知らなかったので、 IE に標準準拠の機能が追加されArray.indexOfた IE でのパフォーマンスという点では、これはひどい敗者になっています。しかし、驚いたことに、それは明らかに卑劣なスプライスクランチマシンである Chrome で悲鳴を上げるだけです。indexOfArray.prototype

私の 2 番目のアイデアは、最初のアイデアよりもはるかにうまく機能しますが、ページの他のアイデアよりも大幅に優れているわけではありません。

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)

最後に、私の 3 番目のアイデアは 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 つの配列を並べ替える方が、文字列ごとに複数の正規表現操作を行うよりも高速です。

編集: 私のアイデア #2 は基本的に Kolink のアルゴリズムの複製であることに気付きました。ただし、私の関数には一貫したパフォーマンス エッジがあります。それらの違いを分析すると、いくつかの興味深い結果が見つかるかもしれません。

また、#2 では、1 行上に移動するべきではなかっcounts[char] -= 1;たことがわかりましたが、jsperf で既に得たパフォーマンス結果を吹き飛ばしたくありません。関数のパフォーマンスを損なうだけなので、結果を不当に歪めることはないので、そのままにしておきます。

jsperf で速度テストを自分で行ってください。

于 2012-07-12T23:25:12.883 に答える