[Hash Table] Ransom Note

383. Ransom Note

지문은 링크에서 확인해주세요.

1. 해답을 보지 않고 스스로 문제를 해결한 과정

본 문제는 해결하지 못했습니다.

/**
 * @param {string} ransomNote
 * @param {string} magazine
 * @return {boolean}
 */
var canConstruct = function(ransomNote, magazine) {
  const strs = [];

  for(let i = 0; i < ransomNote.length; i++) {        
    const cur = ransomNote[i];
    const next = ransomNote[i + 1];

    console.log(cur, next);

    if(cur !== next) {
      strs.push(ransomNote.substring(0, i + 1));
      ransomNote = ransomNote.substring(i + 1);
      i -= i + 1;
    }    
  }    

  return strs.every(str => magazine.indexOf(str) !== -1);
};

다음과 같은 테스트 케이스를 예로,

Input		:	ransomNote = "fffbfg", magazine ="effjfggbffjdgbjjhhdegh"
Output		:	false
Expected	:	true

ransomNote에 연속된 문자를 문자열로 추려 [ 'fff', 'b', 'f', 'g' ] 이들이 magazine에 모두 사용되는지를 판별하는 문제라고 잘못 이해했습니다.

Each letter in magazine can only be used once in ransomNote.지문을 제대로 해석하지 못하였습니다.

2. 여러 해답을 직접 찾아서 자신이 작성한 알고리즘에 대해서 회고한 내용

2-1. Using hash table

해답의 전문은 링크를 확인해주세요.

/*
 * Runtime	: 75 ms
 * Memory	: 43.83 MB
 */
var canConstruct = function(ransomNote, magazine) {
  const hash = {}

  for(let i = 0; i < magazine.length; i++){
    const char = magazine.charAt(i)
    if(hash[char]){
        hash[char]++
    } else {
        hash[char] = 1
    }
  }

  for(let i = 0; i < ransomNote.length; i++){
    const char = ransomNote.charAt(i)
    if(hash[char] && hash[char] > 0){
        hash[char]--
    } else {
        return false
    }
  }

  return true
};

Each letter in magazine can only be used once in ransomNote.지문을 검증하는 마지막 for문의 각 루프 마다 해시 테이블의 상태는 다음과 같습니다.

1번째 루프:	{ e: 2, f: 4, j: 4, g: 4, b: 2, d: 2, h: 3 }
2번째 루프:	{ e: 2, f: 3, j: 4, g: 4, b: 2, d: 2, h: 3 }
3번째 루프:	{ e: 2, f: 2, j: 4, g: 4, b: 2, d: 2, h: 3 }
4번째 루프:	{ e: 2, f: 2, j: 4, g: 4, b: 1, d: 2, h: 3 }
5번째 루프:	{ e: 2, f: 1, j: 4, g: 4, b: 1, d: 2, h: 3 }
6번째 루프:	{ e: 2, f: 1, j: 4, g: 3, b: 1, d: 2, h: 3 }