algorithm
Kontrollera att två strängar är anagram
Sök…
Introduktion
Två strängar med samma uppsättning tecken kallas anagram. Jag har använt javascript här.
Vi kommer att skapa en hash av str1 och öka antalet +1. Vi kommer att slinga på den andra strängen och kontrollera att alla tecken är där i hash och minska värdet på hash-nyckeln. Kontrollera att alla värden på hash-tangenten är noll kommer att vara anagram.
Provinmatning och utgång
Ex1: -
let str1 = 'stackoverflow';
let str2 = 'flowerovstack';
Dessa strängar är anagram.
// Skapa Hash från str1 och öka ett antal.
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
}
Du kan se hashKey 'o' innehåller värdet 2 eftersom o är 2 gånger i strängen.
Nu slinga över str2 och kontrollera om varje tecken finns i hashMap, om ja, minska värdet på hashMap Key, annars returnerar falskt (vilket indikerar att det inte är ett anagram).
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
}
Nu, slinga över hashMap-objekt och kontrollera att alla värden är noll i nyckeln till hashMap.
I vårt fall är alla värden noll så det är ett anagram.
Generisk kod för anagram
(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
})();
Tidskomplexitet: - 3n dvs. O (n).