-5

2 つの文字列 a="abc" があり、もう 1 つが b="ab" であるとします。文字列 a に文字列 b のすべてのアルファベットが含まれているかどうかを確認したい。

4

4 に答える 4

1

効率的な解決策は、2つの文字列を2つの文字セットに読み取ることですbそうした後、がのサブセットである場合に限り、「aのbのすべての文字」a。1セットのみを使用するように最適化できます(bの場合)-擬似コードを参照してください。

このアプローチの複雑さはO(|a|+|b|)、平均してハッシュテーブルを使用するか、O(log(min{|a|,|b|})*(|a|+|b|))最悪の場合はツリーベースを使用します。O(|a|*|b|)すべての文字を検索すると得られる素朴なソリューションと比較すると、はるかに優れています。

擬似コード:

setB <- empty set
for each element e in b:
  setB.add(e)
for each element e in a:
  setB.remove(e) //assuming doing nothing if doesn't exist
return setB.isEmpty()

最適化の考え方は、の要素(chars)をセットにロードし、検出された場合はセットから要素を削除しながら b反復することです。反復が完了すると、(そしてその場合にのみ)含まれていない文字が含まれている場合、その文字はセットに残り、アルゴリズムは戻ります。a
abafalse

于 2013-01-02T15:22:23.187 に答える
0
function func(a,b) {
    var alphabet = b.split("-");    
    for (var i=0; i < alphabet.length; i++) {
      if (a.indexOf(alphabet[i]) == -1)
          return false;
    }   
    return true;
}

func("a-b-c", "a-b");
于 2013-01-02T15:23:42.280 に答える
0

次のコードを使用できます。

var b = "a-b";
var a = "a-b-c";
var firstArray = b.split("-");
var secArray = a.split("-");
var length = firstArray.lenght;
for(var i =0; i<length; i++)
{
  if(secArray.indexOf(firstArray[i]) != -1)
    continue; //or do something
  else
    break; // or return false.
}
于 2013-01-02T15:30:01.040 に答える
0

両方の文字列を表現する可能性のある方法と順序がいくつかあると想定しています。そうは言っても、最も簡単な方法は、文字列 b の各文字が実際に文字列 a に含まれているかどうかを確認することです。そのために、indexOf(currentCharFromStringB)String a を簡単に呼び出すことができます。

次の例が私の考えを理解するのに役立つことを願っています:

"Blue Whale".indexOf("Blue") != -1; // true
"Blue Whale".indexOf("Bloe") != -1; // false

擬似コードは次のようになります。

for each char in b
     for each char in a
        is a in b?

さて、文字列 B の各文字をどのように抽出または表現するかは、あなた次第です。

これが役立つことを願っています。

于 2013-01-02T15:30:42.533 に答える