algorithm
2つの文字列がアナグラムであることを確認する
サーチ…
前書き
同じ文字セットの2つの文字列をアナグラムといいます。私はここでjavascriptを使用しています。
str1のハッシュを作成し、+1を増加させます。 2番目の文字列にループし、すべての文字がハッシュにあり、ハッシュキーの値が小さくなっていることを確認します。ハッシュキーのすべての値が0であることを確認すると、アナグラムになります。
サンプル入力と出力
Ex1: -
let str1 = 'stackoverflow';
let str2 = 'flowerovstack';
これらの文字列はアナグラムです。
// str1からハッシュを作成し、1つのカウントを増やします。
hashMap = {
s : 1,
t : 1,
a : 1,
c : 1,
k : 1,
o : 2,
v : 1,
e : 1,
r : 1,
f : 1,
l : 1,
w : 1
}
oが2回の文字列であるため、hashKey 'o'に値2が含まれていることがわかります。
今度はstr2をループし、各文字がhashMapに存在するかどうかを確認します。そうであれば、hashMap Keyの値を減らし、そうでなければfalseを返します(これはアナグラムではないことを示します)。
hashMap = {
s : 0,
t : 0,
a : 0,
c : 0,
k : 0,
o : 0,
v : 0,
e : 0,
r : 0,
f : 0,
l : 0,
w : 0
}
今度は、hashMapオブジェクトをループし、hashMapのキーですべての値がゼロであることを確認します。
私たちの場合、すべての値はゼロですので、そのアナグラムです。
アナグラムの一般的なコード
(function(){
var hashMap = {};
function isAnagram (str1, str2) {
if(str1.length !== str2.length){
return false;
}
// Create hash map of str1 character and increase value one (+1).
createStr1HashMap(str1);
// Check str2 character are key in hash map and decrease value by one(-1);
var valueExist = createStr2HashMap(str2);
// Check all value of hashMap keys are zero, so it will be anagram.
return isStringsAnagram(valueExist);
}
function createStr1HashMap (str1) {
[].map.call(str1, function(value, index, array){
hashMap[value] = value in hashMap ? (hashMap[value] + 1) : 1;
return value;
});
}
function createStr2HashMap (str2) {
var valueExist = [].every.call(str2, function(value, index, array){
if(value in hashMap) {
hashMap[value] = hashMap[value] - 1;
}
return value in hashMap;
});
return valueExist;
}
function isStringsAnagram (valueExist) {
if(!valueExist) {
return valueExist;
} else {
var isAnagram;
for(var i in hashMap) {
if(hashMap[i] !== 0) {
isAnagram = false;
break;
} else {
isAnagram = true;
}
}
return isAnagram;
}
}
isAnagram('stackoverflow', 'flowerovstack'); // true
isAnagram('stackoverflow', 'flowervvstack'); // false
})();
時間の複雑さ: - 3nすなわちO(n)。
Modified text is an extract of the original Stack Overflow Documentation
ライセンスを受けた CC BY-SA 3.0
所属していない Stack Overflow