2 つの文字列 a="abc" があり、もう 1 つが b="ab" であるとします。文字列 a に文字列 b のすべてのアルファベットが含まれているかどうかを確認したい。
4 に答える
効率的な解決策は、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
a
b
a
false
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");
次のコードを使用できます。
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.
}
両方の文字列を表現する可能性のある方法と順序がいくつかあると想定しています。そうは言っても、最も簡単な方法は、文字列 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 の各文字をどのように抽出または表現するかは、あなた次第です。
これが役立つことを願っています。