[프로그래머스][백트래킹] 단어 변환

단어변환

프로그래머스

 

 

• 내 풀이
  • 백트래킹
  • 예외사항 주의할 것!

처음에 한글자씩 비교 확인 안하고 아래와 같은 코드를 넣었는데

if len(set(cur+next))!=len(target)+1: #한글자 차이가 아니면
    continue

 ->  "aab", "aba"와 같이 중복된 글자가 다른글자일 경우를 제외해버림

answer = 10000
def solution(begin, target, words):
    visited=[False for _ in range(len(words))]
    
    def recur(cur, target,cnt):
        global answer
        if cur==target:
            answer=min(answer,cnt)
            return
        
        for idx, next in enumerate(words):
            if visited[idx]==True:
                continue
            # if len(set(cur+next))!=len(target)+1: #한글자 차이가 아니면
            #     continue
            flag=0
            for aval,bval in zip(cur,next):
                if aval!=bval:
                    flag+=1
            if flag>1:
                continue
            
            visited[idx]=True
            recur(next, target, cnt+1)
            visited[idx]=False
            
    recur(begin, target, 0)   
    
    if answer==10000:
        return 0
    else:
        return answer