algorithm
두 문자열이 anagrams인지 확인하십시오.
수색…
소개
동일한 문자 집합을 가진 두 개의 문자열을 아나그램 (Anagram)이라고합니다. 나는 여기에서 자바 스크립트를 사용했다.
str1의 해시를 만들고 +1을 증가시킵니다. 우리는 두 번째 문자열을 반복 할 것이고 모든 문자가 해시에 있고 해시 키의 값이 감소하는지 확인합니다. 해시 키의 모든 값을 확인하면 아나그램이됩니다.
샘플 입출력
Ex1 : -
let str1 = 'stackoverflow';
let str2 = 'flowerovstack';
이 문자열은 아나그램입니다.
// str1에서 해시를 만들고 하나의 수를 늘립니다.
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
}
당신은 hashKey 'o'가 문자열 2에서 2 번이기 때문에 값 2를 포함하고 있음을 볼 수 있습니다.
이제 str2를 반복하고 각 문자가 hashMap에 있는지 확인합니다. 그렇다면 hashMap Key의 값을 줄이고 그렇지 않으면 false를 반환합니다 (이것이 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
}
이제 hashMap 객체를 반복하고 hashMap의 키에서 모든 값이 0인지 확인하십시오.
우리의 경우 모든 값은 0이므로 해당 값이 반환됩니다.
아나그램의 일반 코드
(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