애니어그램

GIven two strings, write a function to determine if the second string is an anagram of the first. An anagram is a word phrase, or name formed by rearranging the letters of another, such ad cinema, formed grom iceman.

 

validAnagram('','') // true
validAnagram('aaz','zza') // false
validAnagram('anagram','nagaram') // true
validAnagram('rat','car') // false
validAnagram('awesome','awesom') // false
validAnagram('qwerty','qeywtr') // true
validAnagram('texttwisttime','timetwisttest') // true

배열을 이용한 문제 풀이

 

function validAnagram(str1, str2){
	if(str1.length !== str2.length) return false
  const stack = str1.split('')
  for(let i = 0; i < str2.length; i++){
    const idx = stack.indexOf(str2[i])
    if(idx === -1) return false
    stack.slice(idx,1)
	}
	return stack.length === 0 ? true : false
}
console.log(validAnagram('qwerty','qeywtr'))

시간 복잡도가 O(N^2)입니다.

객체를 이용한 문제 풀이

function validAnagram(str1, str2) {
  if (str1.length !== str2.length) return false
  const frequency = {}
  for (let i = 0; i < str1.length; i++) {
    frequency[str1[i]] ? (frequency[str1[i]] += 1) : (frequency[str1[i]] = 1)
  }
  for (let i = 0; i < str2.length; i++) {
    str2[i] in frequency && frequency[str2[i]]--
  }
  for (let i in frequency) {
    if (frequency[i] !== 0) return false
  }
  return true
}
console.log(validAnagram('rat', 'car'))

시간 복잡도가 O(3N) ⇒ O(N)입니다.

답지

function validAnagram(first, second) {
  if (first.length !== second.length) return false
  let frequency = {}
  for (let i = 0; i < first.length; i++) {
    frequency[first[i]] ? (frequency[first[i]] += 1) : (frequency[first[i]] = 1)
  }
  for (let i = 0; i < second.length; i++) {
    const letter = second[i]
    if (!lookup[letter]) {
      return false
    } else {
      lookup[letter]--
    }
  }
  return true
}
console.log(validAnagram('rat', 'car'))