[LeetCode- Ch7. DFS & BFS] 4. 단어 사다리 #

https://leetcode.com/problems/word-ladder/

Word Ladder - LeetCode

 

 

2. DFS 시도

3. BFS 시도

 

DFS 시도

class Solution {
    static int answer=Integer.MAX_VALUE;
    static int rawnum=97;
    static List<String> list;
    static String end;
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        list=wordList;
        DFS(beginWord, 0);
        end=endWord;
        
        return answer;
    }
    public void DFS(String str, int cnt){
        if(cnt>list.size()) return;
        int n=str.length();
        for(int j=0;j<n;j++){
            char[] arr = str.toCharArray();
            for(int i=0;i<26;i++){
                arr[j]=(char)(rawnum+i);
                String tmp=String.valueOf(arr);
                //System.out.println(str+" "+tmp);
            for(String word : list){
                if(word.equals(end) && word.equals(tmp)){
                    System.out.println(end+" "+tmp+" "+cnt);
                    answer=Math.min(answer, cnt);  
                    return;
                } 
                if(word.equals(tmp) && cnt<list.size()) {
                    DFS(word, cnt++);
                }
            }
            }
        }
    }
}

 

 

BFS 시도

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        int rawnum=97;
        Queue<String> q = new LinkedList<>();
        q.offer(beginWord);
        int cnt=0;
        while(!q.isEmpty()){
            String str = q.poll();
            int n=str.length();
            for(int j=0;j<n;j++){
                char[] arr = str.toCharArray();
                for(int i=0;i<26;i++){
                    arr[j]=(char)(rawnum+i);
                    String tmp=String.valueOf(arr);
                System.out.println(str+" "+tmp);
                for(String word : wordList){
                    if(word.equals(tmp)) {
                        q.offer(word);
                    }
                    if(word.equals(endWord) && word.equals(tmp)) return cnt;
                }
                
                }
            }
        }
        return rawnum;
    }
}

---

 

1. 주어진 시작단어와 끝단어 그리고 단어 목록을 이용해 시작단어부터 끝단어까지 한글자씩 바꿔서 연결한다.

2. 그대로 돌면 타임리밋 발생 : 한번 사용한 값은 삭제하면서 찾는다.

 

 

class Solution {
    static List<String> list;
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
        //널 예외처리
        if(wordList==null || !wordList.contains(endWord)){
            return 0;
        }
        if(wordList.contains(beginWord)){
            wordList.remove(beginWord);
        }
        
        //1.DS
        Queue<String> q = new LinkedList<>();
        //중복을 허용하지 않는 자료구조
        Set<String> dic = new HashSet<>(wordList);
        
        list=wordList;
        q.offer(beginWord);
        
        //결과 단어 추가 원래 들어있는데?
        //dic.add(endWord);
        //시작 단어는 제외 큐에 넣었기 때문에
        dic.remove(beginWord);
        
        int level=1;
        //레벨오더를 위해 큐에서 시작
        
        while(!q.isEmpty()){
            int size=q.size();
            //큐에 넣고 큐의 크기만큼 반복하면서 확인하는데 확인했으면 Set에 넣는다.
            
            for(int i=0;i<size;i++){
                String str = q.poll();
                if(str.equals(endWord)) return level;
                for(String search : searches(str)){
                    q.offer(search);
                }
            }          
            //큐를 빼는 순간 체크한다.
            level++;
        }
        return 0;
    }
    public List<String> searches(String s){
        List<String> res = new LinkedList<>();
        Set<String> dic = new HashSet<>(list);
        int n=s.length();
        
        //1) 아스키 코드로
        // int rawnum=97;
        //   for(int j=0;j<n;j++){
        //         char[] arr = s.toCharArray();
        //         for(int k=0;k<26;k++){
        //             arr[j]=(char)(rawnum+k);
        //             String tmp=String.valueOf(arr);
        //         for(String word : dic){
        //             if(word.equals(tmp)) {
        //                 res.add(tmp);
        //             }
        //         }
        //     }    
        // }
        
        //2) 직접
        for(int i=0;i<n;i++){
            char[] arr = s.toCharArray();
            for(char ch ='a'; ch<='z';ch++){
                arr[i]=ch;
                //char[] -> String
                String tmp=String.valueOf(arr);
                //String tmp=new String(arr);
                
                //Set에서 하나씩 지우는 방법
                if(dic.remove(tmp)){
                    res.add(tmp);
                }
                // for(String word:dic){
                //     if(word.equals(tmp)){
                //         res.add(tmp);
                //     }
                // }
                // for(String str : res){
                //     dic.remove(str);
                // }
            }
        }
        
        return res;
    }
}

 

2. 메서드 호출시 Set을 전달하고, 사용한 WordList 삭제

for (String neighbor : neighbors(str, dict)) { 
//1 호출시 set으로 호출

public List<String> neighbors(String s, List<String> wordList) 
//함수의 두번째 파라미터를 Set으로 변경

public List<String> neighbors(String s, Set<String> dict)

class Solution{
public int ladderLength(String beginWord, String endWord, List<String> wordList) {
		if (wordList == null || !wordList.contains(endWord))
			return 0;

		Queue<String> queue = new LinkedList<>();
		Set<String> dict = new HashSet<>(wordList);
		queue.offer(beginWord);
		dict.add(endWord);
		dict.remove(beginWord);
		int level = 1;

		while (!queue.isEmpty()) {
			int size = queue.size();
			for (int i = 0; i < size; i++) {
				String str = queue.poll();
				if (str.equals(endWord))
					return level;
				for (String neighbor : neighbors(str, dict)) { //1 호출시 set으로 호출
					System.out.println("neighbor "+neighbor);
					queue.offer(neighbor);
				}
			}
			level++;
		}

		return 0;
	}

	public List<String> neighbors(String s, Set<String> dict) {//2

		List<String> res = new LinkedList<>();
		for (int i = 0; i < s.length(); i++) {
			char[] chars = s.toCharArray();
			for (char ch = 'a'; ch <= 'z'; ch++) {
				chars[i] = ch;// ait~zit
				String word = new String(chars);
				if (dict.remove(word)) {
					res.add(word);
				}
			}
		}
		return res;
	}

}