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

https://programmers.co.kr/learn/courses/30/lessons/43163

코딩테스트 연습 - 단어 변환

 

Lv3 문제이고 BFS 를 활용해서 해결 가능하다.

다만 두 문자열을 비교할 경우에 같은 문자열 개수가 문자열 길이 - 1 이어야 BFS 를 계속 수행할 수 있으며, begin 문자열로 시작해서 target 문자열로 도달하기까지 최소 횟수를 구하는 문제이며 만약 target 문자열로 도달하는 것이 불가능할 경우 0을 리턴하도록 한다.

BFS 를 하면서, 문자열 중 문자는 1개만 변경 가능하다는 점 참고하면서 아래와 같은 코드를 통해 문제 해결이 가능하다.

 

(예제 코드)

import java.util.*;

class Word {
    String value;
    int count;
    public Word(String value, int count) {
        this.value = value;
        this.count = count;
    }
}


class Solution {
    public static int getCount(String s1, String s2) {
        String maxStr = s1.length() > s2.length() ? s1 : s2;
        String minStr = s1.length() > s2.length() ? s2 : s1;
        int count = 0;
        for (int i = 0; i < minStr.length(); i++) {
            if (minStr.charAt(i) == maxStr.charAt(i)) count++;
        }
        return count;
    }

    public static int solution(String begin, String target, String[] words) {
        int answer = 0;

        Queue<Word> queue = new LinkedList<>();
        int[] visited = new int[words.length];

        for (int i = 0; i < words.length; i++) {
            int count = getCount(begin, words[i]);
            if (count == begin.length() - 1) {
                queue.add(new Word(words[i], 1));
                visited[i] = 1;
            }
        }

        while(!queue.isEmpty()) {
            Word word = queue.poll();
            if (target.equals(word.value)) {
                return word.count;
            }
            for (int i = 0; i < words.length; i++) {
                int count = getCount(word.value, words[i]);
                if (count == begin.length() - 1 && visited[i] == 0) {
                    queue.add(new Word(words[i], word.count+1));
                    visited[i] = word.count+1;
                }
            }
        }

        return answer;
    }
}

 

 

ㅇㅇㅇ