프로그래머스 - 단어 변환

문제풀이에 백트래킹을 적용하였고, 자바스크립트로 작성했습니다.

 

 

문제

두 개의 단어 begin, target과 단어 집합 words가 매개변수로 주어질 때, 최소 몇 단계를 거쳐 begin이 target으로 변환 될 수 있는지를 반환하라.

 

제한사항

• 한 번에 한 개의 알파벳만 바꿀 수 있다.
• words에 있는 단어로만 변환할 수 있다.
• 각 단어는 알파벳 소문자로만 이루어져 있다.
• 3 <= 각 단어의 길이 <= 10
• begin !== target
• 변환할 수 없는 경우 0을 반환한다.

예제

 

begin: hit

target: cog

words: [hot,dot,dog,lot,log,cog]

 

hit->hot->dot->dog->cog와 같이 4단계를 거쳐 변환 가능.

 

 

 

문제풀이

 

이 문제의 가장 작은 하위문제는 words 순회할 때 이전 문자열을 현재 문자열으로 수정할 수 있는가 없는가 이다. 수정이 가능할 경우 이전문자열을 현재 문자열로 수정한 경우와 수정하지 않은 경우 둘 다 탐색해야한다. 수정이 불가능한 경우 수정하지 않은 경우만 탐색한다.

 

function solution(begin, target, words) {
    let minAns = Infinity
    const getDiff = (a, b) => a.split("").reduce((cnt, e, j) => cnt + (e !== b[j]), 0)
    const backtrack = (i, x, n, visited) => {
        if (x === target) {
            minAns = Math.min(n, minAns)
        }
        visited.add(x)
        if (i < words.length) {
            if (getDiff(x, words[i]) === 1 && !visited.has(words[i])) {
                backtrack(0, words[i], n+1, visited)
            }
            backtrack(i+1, x, n, visited)
        }
        visited.delete(x)
    }
    backtrack(0, begin, 0, new Set([begin]))
    return minAns > words.length ? 0 : minAns
}

 

시간복잡도: O(n! * n)

공간복잡도: O(n)