[코딩테스트] 단어 변환

문제

---

단어 변환 문제 바로가기

제출 코드(JAVA)

---

코드 제출

class Solution {
      public int solution(String begin, String target, String[] words) {
        boolean[] check = new boolean[words.length];


        for (int i = 0; i < words.length; i++) {
            if (words[i].equals(target)) {
                check[i] = true;
                break;
            } else if ( i == words.length-1) {
                return 0;
            }
        }
        int[] result = {Integer.MAX_VALUE};
        dfs(words, check, target, begin, 0, result);
        return result[0];
    }

    private void dfs(String[] words, boolean[] check, String target, String begin, int count,  int[] result) {
        if (isPossibleChange(target, begin)) {
            count++;
            result[0] = result[0] > count ? count : result[0];
        }
        for (int i = 0; i < words.length; i++) {
            if (check[i]) { continue; }
            if (isPossibleChange(target, words[i])) {
                check[i] = true;
                dfs(words, check, words[i], begin, count+1, result);
                check[i] = false;
            }
        }
    }

    private boolean isPossibleChange(String target, String word) {
        char[] a = target.toCharArray();
        char[] b = word.toCharArray();
        int result = 0;

        for (int i = 0; i < a.length; i++) {
            if ( a[i] - b[i] != 0 ) result++;
            if (result >= 2) return false;
        }
        return true;
    }
}

target 단어에서 거꾸로 올라가는 방식 채택
1) 변환할 수 있는 단어시, 재귀함수 호출
2) begin 단어까지 왔을 때, 결과물 저장하는 result배열에 횟수 저장
3) result에 저장된 횟수 return

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.04ms, 52.9MB)
테스트 2 〉	통과 (0.14ms, 52MB)
테스트 3 〉	통과 (0.48ms, 52.4MB)
테스트 4 〉	통과 (0.04ms, 51.6MB)
테스트 5 〉	통과 (0.02ms, 52.7MB)

처음으로 혼자서 풀어낸 dfs 문제. 어느정도 숙달된듯

제출 코드(Python)

---

코드 제출

from collections import defaultdict
def isPossibleChange(target, val):
    result = 0
    for t, v in zip(target, val):
        if t != v:
            result += 1
        
    return result < 2


def dfs(resultArr, check, begin, target, count):
    if isPossibleChange(begin, target):
        resultArr[0] = min(resultArr[0], count+1)

    for idx, val in enumerate(resultArr[1:]):
        if check[idx]:
            continue
        if isPossibleChange(target, val):
            check[idx] = True
            dfs(resultArr, check, begin, val, count + 1)
            check[idx] = False


def solution(begin, target, words):
    if not words.__contains__(target):
        return 0

    resultArr = [len(words)] + words
    check = defaultdict(lambda: False)
    check[words.index(target)] = True
    dfs(resultArr, check, begin, target, 0)
    return resultArr[0]

정확성 테스트

정확성  테스트
테스트 1 〉	통과 (0.02ms, 10.3MB)
테스트 2 〉	통과 (0.10ms, 10.2MB)
테스트 3 〉	통과 (0.59ms, 10.3MB)
테스트 4 〉	통과 (0.02ms, 10.2MB)
테스트 5 〉	통과 (0.00ms, 10.3MB)