/* 
        # 최소 교정 비용 문제

        * 두 단어의 한글자씩 바꿀수 있는 방법: 삽입, 삭제, 치환
        * 두 단어간의 교정 비용은 한 단어에서 다른 단어로 바꾸는데 필요한 글자 연산의 횟수로 정의
               
    */

function editDistance(str, str2) {
  if (!str) {
    return str2.length
  }

  if (!str2) {
    return str.length
  }

  // 첫글자 같을 때
  if (str[0] == str2[0]) {
    return editDistance(str.substr(1), str2.substr(1))
  }

  // 삭제, 치환 연산 recursion
  let d, u, i
  // 삭제 연산
  d = editDistance(str.substr(1), str2)

  // 치환 연산
  u = editDistance(str.substr(1), str2.substr(1))

  // 삽입 연산
  i = editDistance(str, str2.substr(1))

  return Math.min(d, u, i)
}

const str = "SUNDAY"
const str2 = "SATURDAY"

// const str = "CAT";
// const str2 = "DOG";

// const str = "CAT";
// const str2 = "CAR";
console.log(editDistance(str, str2))

  -: 삭제, +: 삽입, @: 교환

    S     U N D A Y
      + +   @
    S A T U R D A Y


    S A T U R D A Y
      - -   @
    S     U N D A Y