[알고리즘] anagram

애너그램은 단어나 문장을 구성하고 있는 문자의 순서를 바꾸어 다른 단어나 문장을 만드는 것이다.

 

문제

두개의 문자열이 주어진다. 두 문자열의 요소는 같지만 순서만 뒤바껴있는지 확인하는 함수를 만든다.조건 : 시간복잡도 O(n)

예시 : 

validAnagram("", ""); // true
validAnagram("aaz", "zza"); // false
validAnagram("anagram", "nagaram"); // true
validAnagram("rat", "car"); // false) // false
validAnagram("awesome", "awesom"); // false
validAnagram("amanaplanacanalpanama", "acanalmanplanpamana"); // false
validAnagram("qwerty", "qeywrt"); // true

 

풀이

(1)

function validAnagram(str1, str2) {
  //길이가 같으면 false
  if (str1.length !== str2.length) {
    return false;
  }
  //각 객체에 키값으로 넣고 value로 갯수 파악
  const obj1 = {};
  const obj2 = {};
  for (let i = 0; i < str1.length; i++) {
    obj1[str1[i]] = ++obj1[str1[i]] || 1;
  }
  for (let i = 0; i < str2.length; i++) {
    obj2[str2[i]] = ++obj2[str2[i]] || 1;
  }
  //비교
  for (let key in obj1) {
    // 있는지 비교
    if (!(key in obj2)) {
      return false;
    }
    // 같은 갯수를 가지고 있는지 비교
    if (obj1[key] !== obj2[key]) {
      return false;
    }
  }
  //안걸리면 true
  return true;
}

(2) 객체 하나만 써서 풀기

function validAnagram(first, second) {
  if (first.length !== second.length) {
    return false;
  }

  const lookup = {};

  for (let i = 0; i < first.length; i++) {
    let letter = first[i];
    // if letter exists, increment, otherwise set to 1
    lookup[letter] ? lookup[letter] += 1 : lookup[letter] = 1;
  }

  for (let i = 0; i < second.length; i++) {
    let letter = second[i];
    // can't find letter or letter is zero then it's not an anagram
    if (!lookup[letter]) {
      return false;
    } else {
      lookup[letter] -= 1;
    }
  }

  return true;
}