문제

Programmers Lv3, 단어 변환

핵심

• 단어의 길이는 10 이하, 단어 집합의 크기는 50 이하이므로 구현에 초점을 맞춘다.
• 두 개의 단어 begin, target이 주어지고 단어 집합이 주어진다. begin에서 target으로 변환할 때 한 번에 단어 한 개만 바꿀 수 있고, 단어 집합에 있는 단어로만 변환할 수 있을 때 최소 변환 단계를 찾아야 한다.
• 올바르게 변환된 단어를 생성하고, 몇 번 변환했는지 추적하기 위해 HashSet과 BFS 알고리즘을 적용한다.
  어떻게 올바르게 변환된 단어를 생성할 수 있을까? 시작 문자열 "hit"으로 1번 변환해서 만들 수 있는 모든 경우를 구한다. "ait", "bit", "cit", ... "hat", "hbt", "hct", ... "hia", "hib", "hic" ... "hiz"
• 단어 집합에 없는 문자열을 변환할 수 없다고 했으므로, 단어 집합에 있는 문자로만 변환된 문자열을 생성한다.

Set<String> wordSet = new HashSet<>(Arrays.asList(words));

List<String> getNxtWords(String word, Set<String> wordSet) {
	
	List<String> ret = new ArrayList<>();
	char[] chars = word.toCharArray();
	
	for (int i = 0; i < chars.length; ++i) {
		char cur = chars[i];
		for (char c = 'a'; c <= 'z'; ++c) {
			if (c == cur) continue;
			chars[i] = c;
			String nxt = new String(chars);
			if (wordSet.contains(nxt)) {
				ret.add(nxt);
			}
		}
		chars[i] = cur;
	}
	return ret;
}

• 변환된 문자열을 생성하고 나서 그 문자를 기준으로 또 변환해야 한다. 계속해서 변환만 할 수 있지 않을까? 이를 위해서 변환한 문자열을 다시 변환하지 않도록 HashSet 자료구조를 이용한다. 변환된 횟수를 ans 값에 기록하여 begin이 target이 될 때까지 반복하면 된다. 찾을 수 없다면 0을 반환한다.

int ans = 0;
while (!q.isEmpty()) {
	
	for (int i = 0; i < q.size(); ++i) {
		String cur = q.poll();
		
		if (cur.equals(target)) {
			return ans;
		}
		
		for (var nxt : getNxtWords(cur, wordSet)) {
			if (!isVisited.contains(nxt)) {
				isVisited.add(nxt);
				q.add(nxt);
			}
		}
	}
	++ans;
}

개선

시간복잡도

$O(N * L)$

코드

import java.util.*;

class Solution {
    public int solution(String begin, String target, String[] words) {
        
        Set<String> wordSet = new HashSet<>(Arrays.asList(words));
        Queue<String> q = new LinkedList<>();
        Set<String> isVisited = new HashSet<>();
        
        isVisited.add(begin);
        q.add(begin);
        
        int ans = 0;
        while (!q.isEmpty()) {
            
            for (int i = 0; i < q.size(); ++i) {
                String cur = q.poll();
                
                if (cur.equals(target)) {
                    return ans;
                }
                
                for (var nxt : getNxtWords(cur, wordSet)) {
                    if (!isVisited.contains(nxt)) {
                        isVisited.add(nxt);
                        q.add(nxt);
                    }
                }
            }
            ++ans;
        }
        return 0;
    }
    
    List<String> getNxtWords(String word, Set<String> wordSet) {
        
        List<String> ret = new ArrayList<>();
        char[] chars = word.toCharArray();
        
        for (int i = 0; i < chars.length; ++i) {
            char cur = chars[i];
            for (char c = 'a'; c <= 'z'; ++c) {
                if (c == cur) continue;
                chars[i] = c;
                String nxt = new String(chars);
                if (wordSet.contains(nxt)) {
                    ret.add(nxt);
                }
            }
            chars[i] = cur;
        }
        return ret;
    }
}