Programmers 단어변환: DFS/BFS

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

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

Lv.3

30분

 

원리는 String[] words의 값을 list로 넣은 후 

한 글자만 다른 애들만 getList 메소드로 List를 뽑아 돌려가며 target값이 나올때까지 min값과 비교하며 구하는 것이다.

실행시간 줄이는 방법을 알아내야한다.. getList 메소드에서 이중for문..ㄷㄷ

---

import java.util.ArrayList;
import java.util.List;
class Solution {
    public int min=Integer.MAX_VALUE;
	public String tar;
	
	public int solution(String begin, String target, String[] words) {
        tar = target;
        List<String> list = new ArrayList<String>();
        for (int i = 0; i < words.length; i++) {
			list.add(words[i]);
		}
        repeat(begin, 0, list);
        if(min != Integer.MAX_VALUE) return min;
        else return 0;
	}
	
	
	public void repeat(String b, int cnt, List<String> list) {
		if(b.equals(tar)) {
			if(cnt < min) min = cnt;
		} else {
			list.remove(b);
			List<String> tmp = getList(list, b);
			for (int i = 0; i < tmp.size(); i++) {
				repeat(tmp.get(i), cnt+1, list);
			}
		}
	}
	
	
	public List<String> getList(List<String> list, String word) {
		List<String> sarr = new ArrayList<String>();
		for (int i = 0; i < list.size(); i++) {
			int check = 0;
			String str = list.get(i);
			for (int j = 0; j < str.length(); j++) {
				if(str.charAt(j) != word.charAt(j))	check++;
				if(check>1) break;
			}
			if(check==1) sarr.add(str);
		}
		return sarr;
	}
}